General Graph Maximum Matching Reconstruction

You are given a simple undirected graph whose vertices are numbered from $1$ to $N$.

A matching is a set of edges in which no two edges share an endpoint. Find the maximum possible number of edges in a matching and output one matching attaining that maximum.

The input is given in the following format.

$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$

For each $i$ ($1 \leq i \leq M$), there is an edge connecting vertices $u_i$ and $v_i$.

On the first line, print the size $K$ of a maximum matching.

On each of the next $K$ lines, print the two endpoints $a_i,b_i$ of an edge in the matching.

Every printed pair $(a_i,b_i)$ must be an edge of the input graph, and no vertex may appear more than once. If multiple answers exist, print any of them.

• $1 \leq N \leq 500$.
• $0 \leq M \leq 100\ 000$.
• $1 \leq u_i,v_i \leq N$ ($1 \leq i \leq M$).
• $u_i \neq v_i$ ($1 \leq i \leq M$).
• No unordered pair of vertices appears more than once.