2208 - 最大可达点

题目描述

A 国有 n 个城市(编号为 1~n),城市之间修建了 m 条单向的高速公路。请求出从每个城市能到达的编号最大的城市是哪个城市?

例如下图所示的地图,1 2 3 4 5号城市分别能到达的编号最大的城市为:3 3 3 5 5

输入

1 行有 2 个整数 nm,分别代表城市数量和高速公路的数量。(1≤n≤10^51≤m≤10^5

接下来 m 行,每行有 2 个整数 xy,分别代表从 x 号城市到 y 号城市有一条单向的高速公路。(1≤x,y≤n

输出

输出 n 个整数,用空格隔开,分别代表编号为1 2 3 4 ... n的城市,按照给定的数据,能到达的最大编号的城市。

样例

输入

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

输出

3 3 3 5 5
来源

图论

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题