D. 图的遍历(进阶)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给出 N 个点, M 条边的有向图,对于每个点 v ,求 A(v) 表示从点v出发,能到达的编号最大的点。

输入格式

1 行, 2 个整数 N,M

接下来 M 行,每行 2 个整数 U_i,V_i ​,表示边 (U_i,V_i) 。点用 1,2,⋯ ,N 编号。

输出格式

N 个整数 A(1),A(2),⋯ ,A(N)

样例

输入样例

4 3
1 2
2 4
4 3

输出样例

4 4 3 4

数据范围与提示

对于50% 的数据, 1≤N.M≤10^3

对于100% 的数据, 1≤N,M≤10^5