How Many Paths?
Contest: Codeforces Round 731 (Div. 3)
Difficulty rating: 2100
Tags: 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).

Input format:
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 format:
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$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
5

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

1 0

3 3
1 2
2 3
3 1

5 0

4 4
1 2
2 3
1 4
4 3

Example output:
1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1

Editorial:
The first motivation for solving this problem is to write a lot of standard code like "find strongly connected components", do some DP over the condensed graph (the graph of strongly connected components), and so on.
In fact, this problem can be solved much more elegantly with less code if you have a little better understanding of how depth-first search works.
Consider a usual depth-first search on a digraph that is started from the vertex $$$1$$$. This will be a normal depth-first search, which will paint vertices using three colors: white (the vertex has not yet been found by the search), gray (the vertex is processing by DFS), and black (the vertex has already been processed by the DFS completely, that is, completely bypassed its subtree of the depth-first search tree).
Here's the pseudocode:
The following statements are true:
• there is a cycle in the digraph reachable from $$$s$$$ if and only if the root call dfs(s) visits in the line if color [v] == WHITE when color[v] == GRAY;
• moreover, for each reachable cycle from $$$s$$$ there is at least one vertex that will execute the previous item (then the vertex $$$v$$$ belongs to the cycle);
• if the root call dfs(s) visits in the line if color[v] == WHITE, when color [v] == BLACK, then there is more than one path (the opposite is not true).
It is clear that there are infinite paths from $$$s$$$ to $$$u$$$ if and only if there is a vertex $$$v$$$ on some path from $$$s$$$ to $$$u$$$ such that $$$v$$$ is in a cycle. Thus, we mark all such vertices $$$v$$$ for which color[v] == GRAY at the moment of execution of the line if color [v] == WHITE. The fact is true: All vertices reachable from those noted in the previous phrase are those and only those vertices that an infinite number of paths lead to them.
A similar fact is also true for finding vertices to which at least two paths (but a finite number) lead. Let's mark all such vertices $$$v$$$ for which color[v] == BLACK at the moment of execution of the line if color [v] == WHITE. The fact is true: Let's find all reachable vertices from those marked in the previous phrase. Let's discard those up to which we have already determined that the number of paths is infinite. The remaining reachable vertices are those and only those to which there are at least two paths (and their finite number).
So the solution looks like this:
• let's make a depth-first search from the root, mark during it those vertices that were gray when trying to go to them (group A) and were black when trying to go to them (group B);
• mark the vertices reachable from the group A (let's call them AA);
• mark the vertices reachable from the group B (let's call them BB);
• the answer for the vertex is:   $$$0$$$ if it is not reachable from $$$s$$$ (this determines the first DFS);  $$$-1$$$, if it is from AA;  $$$2$$$ if it is from BB (but not from AA);  $$$1$$$, if it is not from AA and not from BB.
• $$$0$$$ if it is not reachable from $$$s$$$ (this determines the first DFS);
• $$$-1$$$, if it is from AA;
• $$$2$$$ if it is from BB (but not from AA);
• $$$1$$$, if it is not from AA and not from BB.
In the author's solution, only one dfs function was used with an additional boolean parameter to determine its mode.