题目描述

给出一个有 $N$ 个点、$M$ 条边的有向图。对每个点 $v$，定义 $A(v)$ 为从 $v$ 出发能够到达的编号最大的点。请计算所有 $A(v)$。点编号为 $1$ 到 $N$，一个点可以到达自己。

输入格式

第一行输入两个整数 $N,M$。接下来 $M$ 行，每行输入两个整数 $U_i,V_i$，表示一条从 $U_i$ 指向 $V_i$ 的边。

输出格式

输出 $N$ 个整数 $A(1),A(2),\ldots,A(N)$，相邻整数之间用空格分隔。

数据范围与约定

$1\le N,M\le10^5$。

可见测试数据

输入数据 1

5 2
2 3
1 3

输出数据 1

3 3 3 4 5

输入数据 2

5 3
1 1
4 1
4 1

输出数据 2

1 2 3 4 5

输入数据 3

51 12
47 22
12 17
43 42
19 34
12 36
47 18
26 26
12 2
44 28
4 50
49 1
16 36

输出数据 3

1 2 3 50 5 6 7 8 9 10 11 36 13 14 15 36 17 18 34 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51