#P2291. 【POJ Challenge】超级笔记

    ID: 1325 传统题 2000ms 128MiB 尝试: 8 已通过: 4 难度: 7 上传者: 标签>CF2300提高+/省选-二分图匹配欧拉回路Hierholzer 算法奇偶性分析

【POJ Challenge】超级笔记

题目描述

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

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

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

输入格式

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

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

输出格式

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

4 4
1 2
2 3
3 4
4 1
1 2
3 4

数据规模与约定

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