#2291. 【POJ Challenge】超级笔记

内存限制:128 MiB 时间限制:20 Sec

题目描述

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

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

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

输入格式

 

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

第2到 M + 1行,两个整数 Ai and Bi, 连接点 Ai and Bi 的边。

输出格式

 

若干对整数 Xi and Yi, 匹配的边。

样例

样例输入


			
4 4
1 2
2 3
3 4
4 1

样例输出


			
1 2
3 4

数据范围与提示

请不要提交!