Hàm số F(u) trong đồ thị có hướng

Cho một đồ thị có hướng (có thể có khuyên) gồm \(N\) đỉnh và \(M\) cạnh. Các đỉnh được đánh chỉ số từ \(1\) đến \(N\). Với mỗi đỉnh \(u\) từ \(1\) đến \(N\), hãy xác định giá trị cho \(F(u)\) theo quy tắc sau:

• \(F(u) = 0\), nếu như không có đường đi từ \(1\) đến \(u\).
• \(F(u) = 1\), nếu như chỉ có duy nhất một đường đi từ \(1\) đến \(u\).
• \(F(u) = 2\), nếu như có nhiều hơn một đường đi từ \(1\) đến \(u\), nhưng số đường đi đếm được là hữu hạn.
• \(F(u) = -1\), nếu như có vô số đường đi từ \(1\) đến \(u\).

Chú ý: Một đường đi có thể đi qua một đỉnh hoặc một cung nhiều lần!

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) \((1 \leq N \leq 10^5, 0 \leq M \leq 10^5)\), tương ứng với số đỉnh và số cạnh.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq N)\), biểu thị một cung đi từ đỉnh \(u\) đến đỉnh \(v\).

Output

• Gồm một dòng duy nhất chứa \(N\) số nguyên, mỗi số tương ứng với \(F(u)\) của từng đỉnh \(u\), các số cách nhau bởi một khoảng trắng.

Example

6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6

1 0 1 2 -1 -1