#2291. 【POJ Challenge】超级笔记

题目描述

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

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

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


输入格式

第1行，两个整数 N (1 ≤ N ≤ 105) 和 M (1 ≤ M ≤ 106, 你可以假定 M = 2 K × N ), 点和边的数量。

第2到 M + 1行，两个整数 A i and B i, 连接点 A i and B i 的边。

输出格式

若干对整数 X i and Y i, 匹配的边。

样例

样例输入

4 4  

1 2  

2 3  

3 4  

4 1  

样例输出

1 2  

3 4  

数据范围与提示

请不要提交！