Forced Propagation in Directed Graphs

Given a directed graph with \(n\) vertices and \(m\) edges where every vertex has at least one outgoing edge, each vertex can be colored either black or white. Initially, all vertices are white. For every integer \(1 \le k \le n\), you are to answer the following question:

• The game is played as follows. In each operation, Alice first chooses a black vertex \(u\) with \(1 \le u \le k\). Then Bob must choose one of the vertices \(v\) such that there is a directed edge \(u \to v\) and color \(v\) black.
• An ordered pair \((A, B)\) with \(A \neq B\) is called good if, starting from the state where only vertex \(A\) is black, no matter how Bob chooses his moves, vertex \(B\) will eventually be colored black.
• Your task is to count the number of good ordered pairs for each \(k\) from \(1\) to \(n\). Note that only vertices numbered \(\le k\) can be chosen by Alice as the source of the move.

One way to view the problem is as a reachability game on a directed graph. When a vertex \(v\) is eligible for choice (i.e. \(v \le k\)), Alice controls the move, but Bob gets to decide which outgoing edge to follow. For a fixed target vertex \(B\), we say that a vertex \(v\) (other than \(B\)) is forced to reach \(B\) if there exists a strategy for Alice such that, regardless of Bob's choices, beginning with the state where only \(v\) is black and only vertices \(\le k\) may be selected for moves, vertex \(B\) will eventually be colored black. Then \((A, B)\) is good if and only if \(A\) is forced into \(B\) when starting from that single black vertex state.

Input/Output: For each \(k\) from \(1\) to \(n\), output the count of good pairs \((A, B)\) (with \(A \neq B\)) that satisfy the forced propagation property.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively. The vertices are numbered from 1 to \(n\). Each of the following \(m\) lines contains two integers \(u\) and \(v\) representing a directed edge from \(u\) to \(v\). It is guaranteed that every vertex has at least one outgoing edge.

outputFormat

Output a sequence of \(n\) integers. The \(k\)-th integer denotes the number of good ordered pairs \((A, B)\) when vertices \(1, 2, \ldots, k\) are allowed as source vertices for Alice's move.

sample

3 4
1 2
2 3
1 3
3 1

1 3 4