#51 General Graph Maximum Matching Reconstruction

Statement

Statement language

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_{}$

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.

Constraints

$1 \leq N \leq 500$ .
$0 \leq M \leq 100\ 000$ .
$1 \leq u_{i}, v_{i} \leq$ ().

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