{"code":"label","name":"Gán nhãn","description":"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)$: \r\n - $F(u) = 0$, nếu như không có đường đi từ 1 đến $u$ \r\n - $F(u)= 1$, nếu như chỉ có duy nhất một đường đi từ 1 đến $u$\r\n - $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\r\n - $F(u) = -1$, nếu như có vô số đường đi từ 1 đến $u$\r\n*Chú ý, một đường đi có thể đi qua một đỉnh hoặc một cung nhiều lần!*\r\n\r\n\r\n\r\n

Input

\r\n- Dòng đầu tiên gồm 2 số $N$ và $M$, tương ứng số đỉnh và số cạnh \r\n- $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 \r\n\r\n

Output

\r\n- 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\r\n\r\n

Scoring

\r\n - 20% số tests có $1 \\le N \\le 1000, 1 \\le M \\le 5000$\r\n - 80% số tests có $1 \\le N, M \\le 300000$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n ???+ \"Input\"\r\n ```sample\r\n 6 7\r\n 1 4\r\n 1 3\r\n 3 4\r\n 4 5\r\n 2 1\r\n 5 5\r\n 5 6\r\n\r\n\r\n\r\n\r\n ```\r\n ???+ success \"Output\"\r\n ```sample\r\n 1 0 1 2 -1 -1\r\n\r\n ```\r\n ??? warning \"Note\"\r\n - ...","points":200.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}