Đếm số đường đi

Cho một đồ thị có hướng $G$ gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Đồ thị có thể chứa vòng lặp (cạnh đi từ một đỉnh tới chính nó) nhưng không có cạnh bội — với mọi cặp đỉnh có thứ tự $(u,v)$, có nhiều nhất một cạnh từ $u$ tới $v$.

Một đường đi từ $u$ tới $v$ là một dãy cạnh sao cho:

• Đỉnh $u$ là đầu của cạnh đầu tiên;
• Đỉnh $v$ là cuối của cạnh cuối cùng;
• Với mọi hai cạnh liền nhau, cạnh sau xuất phát từ đỉnh mà cạnh trước kết thúc.

Quy ước rằng dãy cạnh rỗng cũng là một đường đi từ $u$ tới $u$.

Với mỗi đỉnh $v$, hãy in ra một trong bốn giá trị:

• $0$ — nếu không có đường đi nào từ $1$ tới $v$;
• $1$ — nếu có đúng một đường đi từ $1$ tới $v$;
• $2$ — nếu số đường đi từ $1$ tới $v$ là hữu hạn và lớn hơn $1$;
• $-1$ — nếu số đường đi từ $1$ tới $v$ là vô hạn.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le {10}^4$) — số bộ test.
• Trước mỗi bộ test có một dòng trống.
• Dòng đầu của mỗi bộ test chứa hai số nguyên $n$ và $m$ ($1\le n\le 4·{10}^5$, $0\le m\le 4·{10}^5$) — số đỉnh và số cạnh.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i,b_i$ ($1\le a_i,b_i\le n$) — cạnh có hướng từ $a_i$ tới $b_i$.

Tổng $n$ qua tất cả bộ test không vượt quá $4·{10}^5$. Tổng $m$ qua tất cả bộ test không vượt quá $4·{10}^5$.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa $n$ số nguyên, mỗi số thuộc tập $\{-1,0,1,2\}$ — đáp án cho từng đỉnh từ $1$ tới $n$.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n,m\le 4·{10}^5$ (theo nghĩa $1\le n$ và $0\le m$, với tổng giới hạn $4·{10}^5$ mỗi loại)
• Đồ thị có thể chứa vòng lặp, nhưng không có cạnh bội.

Ví dụ