QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Hackable ✓
Statistics

题目修改自 Library Checker。

给定一张 $N$ 个点 $M$ 条边的无向图,第 $i$ 条边为 $(u_i, v_i)$。你需要求最大匹配。

输入格式

  • $N$ $M$
  • $u_0$ $v_0$
  • $u_1$ $v_1$
  • :
  • $u_{M - 1}$ $v_{M - 1}$

输出格式

  • $X$
  • $a_0$ $b_0$
  • $a_1$ $b_1$
  • :
  • $a_{X - 1}$ $b_{X - 1}$

样例数据

样例 1 输入

7 8
2 0
0 5
5 6
6 1
1 0
1 3
3 4
1 4

样例 1 输出

3
0 2
1 6
3 4

样例 2 输入

5 4
0 1
0 2
0 3
0 4

样例 2 输出

1
0 1

子任务

$1 \leq N \leq 500$, $0 \leq M \leq \frac{N(N-1)}{2}$, $0 \leq u_i, v_i < N$