Background

This is a template problem, with no background.

Problem Description

Given a directed graph, starting from node $1$, find for each node the number of nodes it can dominate (including itself).

Input Format

The first line contains two positive integers $n, m$, representing the number of nodes and the number of edges.

In the next $m$ lines, each line contains two integers $u, v$, representing a directed edge from $u$ to $v$.

Output Format

Output one line with $n$ integers, representing the number of nodes each node can dominate.

10 15
1 2
2 3
3 4
3 5
3 6
4 7
7 8
7 9
7 10
5 6
6 8
7 8
4 1
3 6
5 3

10 9 8 4 1 1 3 1 1 1 

Hint

Constraints: $n \le 2 \times 10^5$, $m \le 3 \times 10^5$.

Translated by ChatGPT 5