Migrated from Lutece 3179 模拟宇宙·其一

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

黑塔又升级模拟宇宙了。

这次的模拟宇宙由 $n$ 个区域和 $m$ 条连接它们的单向通道组成。你可以从任意一个区域开始，走到任意一个区域结束，然后去挑战首领敌人。为了防止分裂金币被滥用，黑塔设计的地图不存在任何环路。现在，你希望知道，如果从各个区域开始这次模拟宇宙，最多可以经过多少个区域。

Input

第一行两个整数 $n$ 和 $m$ ，分别表示区域的数量和通道的数量。

接下来 $m$ 行，每行两个整数 $u_i$ 和 $v_i$ ，表示区域 $u_i$ 存在一条通道通向区域 $v_i$ 。

Output

一共 $n$ 行，每行一个整数，第 $i$ 行的整数表示从第 $i$ 个区域开始最多可以经过的区域数量。

Samples

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

4
2
1
1
3
1

Constraints

$1 \leq n \leq 100000$

$1 \leq m \leq 200000$

$1 \leq u_i, v_i \leq n$

Resources

2024 UESTC ICPC Training for Graph