D. 景区三角形

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

题目描述

小途假期到京城旅游,他想去 n 个景区,编号分别为: 1,2,\cdots, n ,其中某些景区可以通过一条双向通行的道路直接到达。

小途正在使用只包含 n 个景区的地图研究路线,他从当地人那听说了一个有趣的现象:这张地图中存在三个景区两两之间都有双向通行的道路直接连通,这种结构被称为“金三角”。

在该地图 G 中,有且仅有一个这样的金三角。但是地图太大啦,小途实在是看不过来,你能帮小途找到它吗?

输入格式

第一行输入两个以空格隔开的正整数 n,m,表示地图 G 中景区的个数和双向通行道路的条数。

接下来 m 行,每行输入两个以空格隔开的正整数 u,v 表示景区 u 和 v 之间有一条双向通行的道路。

题目保证地图一定是连通图,且没有重边和自环。

输出格式

输出共一行,以空格隔开的三个正整数 a,b,c,其中 a<b<c,表示构成金三角的三个景区编号。

样例

样例输入1

4 4
1 2
3 1
2 3
3 4

样例输出1

1 2 3

样例解释1

样例输入2

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

样例输出2

1 2 5

样例解释2

数据范围与提示

对于 30% 的数据 1\leq n \leq 200

对于另外 30% 的数据 1\leq n \le 2000

对于全部数据 1\leq n, m \leq 100000,1\leq u,v\leq n,u\neq v