Dominance Count in Directed Graphs

Given a directed graph and a distinguished start vertex 1, we say that a vertex u dominates another vertex v if every path from vertex 1 to v passes through u. Note that every vertex trivially dominates itself. The task is to compute for each vertex the number of vertices it dominates.

Definition: For each vertex v, let D(v) = { u : u dominates v }. In this problem, we want, for each vertex u, to calculate the number of vertices v for which u is a dominator (i.e. u is on every path from 1 to v), including u itself.

One standard approach is to compute the dominator tree using the Lengauer-Tarjan algorithm and then use a DFS to count the size of the subtree corresponding to each vertex in the dominator tree.

inputFormat

The first line contains two integers n and m, where n is the number of vertices and m is the number of directed edges. Each of the next m lines contains two integers u and v, indicating a directed edge from u to v. The vertices are numbered from 1 to n. It is guaranteed that vertex 1 is the start vertex.

outputFormat

Output n space‐separated integers. The i-th integer denotes the number of vertices dominated by vertex i. If a vertex is not reachable from vertex 1, output 0 for that vertex.

sample

4 4
1 2
1 3
2 4
3 4

4 1 1 1