P5180 [Template] Dominator Tree

This is a template problem, with no background.

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

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 one line with $n$ integers, representing the number of nodes each node can dominate.

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