2206: 【基础】最大可达点

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

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

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

输入格式

第1行有2个整数n和m,分别代表城市数量和高速公路的数量。(1≤n≤105,1≤m105

接下来m行,每行有2个整数x和y,分别代表从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

分类标签