# Matching on General Graph

AC一覧

## Problem Statement (Japanese) / 問題文 (日本語)

$N$ 頂点 $M$ 辺の単純な無向グラフが与えられる。辺は $(u_i, v_i)$。

## Constraints / 制約

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

## Input / 入力

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


## Output / 出力

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


$X$ は最大マッチングのサイズ

## Sample / サンプル

### # 1

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

3
0 2
1 6
3 4


### # 2

5 4
0 1
0 2
0 3
0 4

1
0 1


Timelimit: 5 secs