How Many Paths?

4000ms

524288K

Description:

You are given a directed graph $$$G$$$ which can contain loops (edges from a vertex to itself). Multi-edges are absent in $$$G$$$ which means that for all ordered pairs $$$(u, v)$$$ exists at most one edge from $$$u$$$ to $$$v$$$. Vertices are numbered from $$$1$$$ to $$$n$$$.

A path from $$$u$$$ to $$$v$$$ is a sequence of edges such that:

vertex $$$u$$$ is the start of the first edge in the path;
vertex $$$v$$$ is the end of the last edge in the path;
for all pairs of adjacent edges next edge starts at the vertex that the previous edge ends on.

We will assume that the empty sequence of edges is a path from $$$u$$$ to $$$u$$$.

For each vertex $$$v$$$ output one of four values:

$$$0$$$, if there are no paths from $$$1$$$ to $$$v$$$;
$$$1$$$, if there is only one path from $$$1$$$ to $$$v$$$;
$$$2$$$, if there is more than one path from $$$1$$$ to $$$v$$$ and the number of paths is finite;
$$$-1$$$, if the number of paths from $$$1$$$ to $$$v$$$ is infinite.

Let's look at the example shown in the figure.

$\text{[math]}$

Then:

the answer for vertex $$$1$$$ is $$$1$$$: there is only one path from $$$1$$$ to $$$1$$$ (path with length $$$0$$$);
the answer for vertex $$$2$$$ is $$$0$$$: there are no paths from $$$1$$$ to $$$2$$$;
the answer for vertex $$$3$$$ is $$$1$$$: there is only one path from $$$1$$$ to $$$3$$$ (it is the edge $$$(1, 3)$$$);
the answer for vertex $$$4$$$ is $$$2$$$: there are more than one paths from $$$1$$$ to $$$4$$$ and the number of paths are finite (two paths: $$$[(1, 3), (3, 4)]$$$ and $$$[(1, 4)]$$$);
the answer for vertex $$$5$$$ is $$$-1$$$: the number of paths from $$$1$$$ to $$$5$$$ is infinite (the loop can be used in a path many times);
the answer for vertex $$$6$$$ is $$$-1$$$: the number of paths from $$$1$$$ to $$$6$$$ is infinite (the loop can be used in a path many times).

Input:

The first contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow. Before each test case, there is an empty line.

The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 4 \cdot 10^5, 0 \le m \le 4 \cdot 10^5$$$) — numbers of vertices and edges in graph respectively. The next $$$m$$$ lines contain edges descriptions. Each line contains two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the start and the end of the $$$i$$$-th edge. The vertices of the graph are numbered from $$$1$$$ to $$$n$$$. The given graph can contain loops (it is possible that $$$a_i = b_i$$$), but cannot contain multi-edges (it is not possible that $$$a_i = a_j$$$ and $$$b_i = b_j$$$ for $$$i \ne j$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$. Similarly, the sum of $$$m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output:

Output $$$t$$$ lines. The $$$i$$$-th line should contain an answer for the $$$i$$$-th test case: a sequence of $$$n$$$ integers from $$$-1$$$ to $$$2$$$.

Sample Input:

Sample Output:

1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1

Informação

Provedor Codeforces

Código CF1547G