如今，人们在各个十字路口讨论着选举。丑闻、阴谋、调查、披露。在我们的城镇 Badroadville，也到了选举市长的时候了。为了避免通常的内斗，我们决定彻底改变概念：获胜者将由行动而非言语决定。而这个行动非常重要——那就是道路建设。

Badroadville 有几个区域，共有 $N$ 座房屋。房屋之间由 $M$ 条双向道路连接。和往常一样，道路并不多。房屋之间的道路没有重复，也没有连接到同一座房屋的环路。在同一个区域内的任意两座房屋之间总是至少有一条路径（顺便提一下，一个区域可以仅由一座房屋组成）。但是，不同区域之间没有道路，所以不幸的城镇居民不得不深一脚浅一脚地在泥泞中跋涉。

竞选下一任市长的候选人将轮流在两座房屋之间修建一条道路，谁先将整个城市变成一个完整且幸福的区域，谁就将成为 Badroadville 的新市长。

我们建议您与我们的候选人一起参加竞选，证明您已准备好治理城镇，并将其带向更美好的明天！

作为尊贵的客人，您可以选择谁先开始修建道路。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示城镇中房屋和道路的数量。 接下来的 $M$ 行描述了道路，每行包含 $U_i$ 和 $V_i$，表示由该道路连接的房屋编号。

$2 \le N \le 200$ $0 \le M \le N * (N - 1)/2$ $1 \le U_i, V_i \le N$

交互

在收到当前 Badroadville 的道路方案后，您需要打印数字“1”或“2”，分别表示您希望作为先手还是后手开始竞选。

现在，如果是您的回合，您需要打印两个整数 $U$ 和 $V$，表示您要通过道路连接的房屋编号。如果现在是对手的回合，您将收到两个整数 $U$ 和 $V$，表示您的对手连接的房屋编号。

当城镇中只剩下一个区域时，或者当对手向您发送两个零“0 0”时，您必须正确结束竞选。

请不要忘记输出换行符并刷新缓冲区。例如，您可以在 C++ 中使用 fflush(stdout)，在 Java 中使用 System.out.flush()，在 Pascal 中使用 flush(output)。

样例

输入 1

4 0
3 4

输出 1

1
1 2
1 3

输入 2

5 1
3 5
2 3
0 0

输出 2

1
1 2
1 5