Problem Description

Given a directed acyclic graph (DAG) with $N$ nodes and $M$ edges, count for each node how many nodes can be reached starting from that node.

Input Format

The first line contains two integers $N, M$. The next $M$ lines each contain two integers $x, y$, representing a directed edge from $x$ to $y$.

Output Format

Output $N$ lines in total, where each line gives the number of nodes that can be reached from that node.

10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

1
6
3
3
2
1
1
1
1
1

Hint

The testdata satisfies $1 \le N, M \le 30000$, $1 \le x, y \le N$.

Translated by ChatGPT 5