题目描述

Aldas 和 David 正在玩一个游戏。

圆周上按顺序写着 $1,2,\ldots,N$ 这些数字，其中一些数字对之间已经用线段连接。不同线段之间允许相交。

Aldas 先手，之后两人轮流操作。

在自己的回合中，玩家必须选择两个当前尚未直接相连的数字，并在它们之间添加一条线段。

如果某位玩家在自己的操作后形成了一个由四个不同数字组成的环，那么该玩家立即获胜。

具体来说，若存在四个互不相同的数字 $a,b,c,d$，使得 $a$ 与 $b$ 相连、$b$ 与 $c$ 相连、$c$ 与 $d$ 相连、$d$ 与 $a$ 相连，则称它们构成一个 4-环。

已知初始局面中不存在任何 4-环。

请判断：如果 David 始终采用最优策略，Aldas 是否仍然能够保证获胜。

如果可以，请输出 Aldas 第一步应当连接的两个数字；如果有多种可行的第一步，输出任意一种即可。

如果 Aldas 无法保证获胜，则输出 0。

输入格式

第一行包含两个整数 $N,M$，分别表示圆周上的数字数量和初始时已经存在的连线数量。

接下来 $M$ 行，每行包含两个整数 $A_i,B_i$，表示数字 $A_i$ 与 $B_i$ 在初始局面中已经相连。

保证：

• $4\le N\le600$；
• $0\le M\le600$；
• $1\le A_i<B_i\le N$；
• 任意两条给出的边互不相同；
• 初始图中不存在 4-环。

输出格式

如果 Aldas 能够保证获胜，输出两个整数，表示他第一步应该连接的两个数字。

如果存在多种可行方案，输出任意一种即可。

如果 Aldas 无法保证获胜，输出：

0

样例 1

4 3
1 2
2 3
3 4

1 4

样例 1 说明

Aldas 可以连接数字 $1$ 和 $4$。

此时形成 4-环

$1-2-3-4-1$，

因此 Aldas 立即获胜。

样例 2

4 3
1 2
2 3
1 3

0

样例 2 说明

Aldas 的第一步必须把数字 $4$ 与另外某个数字相连。

无论他选择连接哪一个数字，David 都可以在下一步将 $4$ 与另外两个数字中的一个相连，并立即形成一个 4-环。

因此 Aldas 无法保证获胜。

子任务

本题采用捆绑测试。只有通过一个子任务中的全部测试点，才能获得该子任务的分数。