Reachable Nodes in a Directed Acyclic Graph

You are given a directed acyclic graph (DAG) with \(N\) nodes and \(M\) edges. For each node, compute the number of distinct nodes that are reachable from it.

More formally, given a graph \(G = (V, E)\) where \(|V| = N\) and \(|E| = M\), for every node \(u \in V\), find the number of nodes \(v\) such that there exists a path from \(u\) to \(v\) (with \(u \neq v\)).

Note: The input graph is guaranteed to be a DAG, so there will be no cycles.

inputFormat

The first line of input contains two integers \(N\) and \(M\) — the number of nodes and the number of edges respectively.

Each of the following \(M\) lines contains two integers \(u\) and \(v\) indicating there is a directed edge from node \(u\) to node \(v\). (Nodes are numbered from 1 to \(N\)).

outputFormat

Output a single line containing \(N\) space-separated integers. The \(i\)-th integer should denote the number of nodes reachable from node \(i\) (excluding itself).

sample

4 4
1 2
1 3
3 4
2 4

3 1 1 0