G. How Many Paths?
dfs and similar; dp; graphs; trees
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. 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).
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 \(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\).