链接: https://cses.fi/problemset/task/2138

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一个有向无环图由 $n$ 个节点和 $m$ 条边组成。节点编号为 $1,2,\dots,n$。

对每个节点，计算从该节点出发可以到达的节点数量（包括该节点自身）。

输入

第一行有两个整数 $n$ 和 $m$：节点数量与边数量。

之后有 $m$ 行描述边。每行有两个不同的整数 $a$ 和 $b$：存在一条从节点 $a$ 到节点 $b$ 的边。

输出

输出 $n$ 个整数：每个节点对应的可达节点数量。

数据范围

$1 \le n \le 5 \cdot 10^4$ $1 \le m \le 10^5$

样例输入

5 6
1 2
1 3
1 4
2 3
3 5
4 5

样例输出

5 3 2 2 1