Cho một đơn đồ 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)\):

• \(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 1 đườ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 gồm 2 số \(N\) và \(M\), tương ứng số đỉnh và số cạnh
• \(M\) dòng tiếp theo, mỗi dòng gồm 2 số \(u\) và \(v\), tương ứng có cung từ đỉnh \(u\) đến

Output

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

Scoring

• 20% số tests có \(1 \le N \le 1000, 1 \le M \le 5000\)
• 80% số tests có \(1 \le N, M \le 300000\)

Example

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

1 0 1 2 -1 -1