#51 General Graph Maximum Matching Reconstruction

Loading problem...

Preparing the statement, recent submissions, and submit form.

#51 General Graph Maximum Matching Reconstruction | DOJ

Time limit: 5000 ms
Python time limit: 10000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

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.

Input

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$ .

Output

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.

Constraints

$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.

Subtasks

#	Score	Constraints
1	20	$N \leq 24$ .
2	80	There are no additional constraints.

Samples

Sample 1

Input

Output

2
1 2
3 4

The edges $(1,2)$ and $(3,4)$ do not share an endpoint. Since the graph has four vertices, no matching can have more than two edges.

Sample 2

Input

Output

1
2 3

In a triangle, every two distinct edges share a vertex, so the maximum matching size is $1$ .

Editorial

View editorial