Problem6946--Simple Game

6946: Simple Game

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

这是一个神奇的城市,我们可以把这座城市的地铁网抽象为一个有向图,共有 $n$ 个地铁站。对于每个地铁站,我们用 $1,2,\cdots,n$ 编号。   
Sept 邀请 David 去咖啡厅,但他并不想很快地告诉 David 咖啡厅的地址,于是便想和他一起玩个简单的小游戏。
他告诉 David,他只记得咖啡厅和他的家都在恰好一个地铁站边上,且这家咖啡厅所在的地铁站的编号很小。Sept 希望 David 能够猜中咖啡厅的位置。
但 David 也不知道 Sept 的家在哪个地铁站附近,而他又希望他能尽快猜中咖啡厅的位置,于是他只能猜测咖啡厅是在从 Sept 的家能到达的编号最小的地铁站附近。所以他希望你能告诉他,对于 Sept 的家可能在的每一个位置,能到达的所有地铁站的编号中最小的一个。
而 David 也不想浪费猜测次数,所以他还要求你对答案排序后去重处理。

Input

第一行两个整数 $n,m$,表示点与边的数量。
接下来 $m$ 行,每行两个整数 $u,v$,表示存在边 $u\to v$。

Output

共一行 $k\ (k\le n)$ 个整数,即从每个地铁站能到达的编号最小的地铁站的编号。如有重复编号,只输出第一个。

Constraints

对于 $100\%$ 的数据,有 $1\le n,m\le 10^5$。
特殊性质 A:该地铁线路是一个环。
特殊性质 B:该地铁线路中不会出现环。

Sample 1 Input

4 3
1 2
2 4
4 3

Sample 1 Output

1 2 3

如图所示,点 $1,2,3$ 能到达的编号最小的点是它们本身,点 $4$ 可通过边 $4\to3$ 到达点 $3$。由于出现了两个 $\tt{3}$,所以只输出第一个。

HINT

相同题目:牛客网

Source/Category