← 返回题目列表

Codeforces · 1600/F

F. 党组织

中文机器翻译题面 查看原题

在巴尔蒂亚大岛上,住着$$$N$$$人,编号从$$$1$$$到$$$N$$$。恰好有 $$$M$$$ 人是彼此的朋友。巴尔蒂亚人民希望组织一个成功的政党,但他们对政党是什么以及政党何时成功有非常严格的规定。在巴尔蒂亚岛上,聚会是由 $$$5$$$ 人组成的聚会。如果聚会中的所有人都是彼此的朋友(这样他们就可以互相交谈,而不必担心与不是朋友的人交谈),或者聚会中没有两个人彼此是朋友(这样每个人都可以只玩手机而没有其他人打扰他们),则聚会被认为是成功的。请帮助巴尔蒂亚人民组织一个成功的聚会,或者告诉他们这是不可能的。

输入

第一行包含两个整数,$$$N$$$ ($$$5 \leq N \leq 2*10^5$$$) 和 $$$M$$$ ($$$0 \leq M \leq 2*10^5$$$) – 居住在巴尔蒂亚的人数以及友谊的数量。接下来的 $$$M$$$ 行每行包含两个整数 $$$U_i$$$ 和 $$$V_i$$$ ($$$1 \leq U_i,V_i \leq N$$$) – 意味着这个人 $$$U_i$$$ 是这个人 $$$V_i$$$ 的朋友。两个朋友不能在朋友列表中两次(没有重复的配对),并且一个人可以与自己成为朋友($$$U_i \ne V_i$$$)。

输出

如果可以组织一次成功的聚会,请打印 $$$5$$$ 数字,表明应邀请哪些 $$$5$$$ 人参加聚会。如果无法组织一次成功的聚会,请打印 $$$-1$$$。如果可能有多个成功方,请打印其中任何一个。

示例

输入 #1

6 3
1 4
4 2
5 4

输出 #1

1 2 3 5 6

输入 #2

5 4
1 2
2 3
3 4
4 5

输出 #2

-1