题目描述

有一天，lqp18_31 看了 1tthinking 的图论笔记。他发现了下面的一些有趣东西：

• 二分图：没有奇环的图；
• 正则图：顶点度数都相同的图；
• 匹配：没有公共点的边集；
• 最大匹配：边数最多的匹配。

所以，lqp18_31 请你找出一个正则二分图的最大匹配。

输入格式

第一行两个整数 $n,m$ 表示点和边的数量，$m$ 满足 $m=2^k\times n$。

接下来 $m$ 行，每行两个整数 $u,v$ 表示一条边 $(u,v)$。

输出格式

若干行，每行表示一条最大匹配里的边。

4 4
1 2
2 3
3 4
4 1

1 2
3 4

数据规模与约定

对于 $100\%$ 的数据，$1\leq u,v\leq n\leq 10^5$，$1\leq m\leq 10^6$。