Constructing phylogenetic relationships between organisms is a very important task in bioinformatics.

Phylogenetic relationships are usually represented by a tree, called a phylogenetic tree. Each organism corresponds to a leaf node in the phylogenetic tree.

The length of the path between two leaf nodes in the phylogenetic tree indicates how closely related the two corresponding organisms are in evolutionary terms.

Using a phylogenetic tree, we can define a graph representing how closely related organisms are in evolutionary terms.

This graph is called a phylogenetic graph.

A phylogenetic graph with similarity $K$ is defined as follows.

Each vertex of the graph represents an organism. An edge exists between two vertices if and only if the distance (path length) between their corresponding nodes in the phylogenetic tree is at most $K$.

A laboratory constructed a phylogenetic graph with similarity $3$, but then lost the data for the phylogenetic tree. It therefore wants to reconstruct the tree.

Given a phylogenetic graph with similarity $3$, write a program that finds a phylogenetic tree defining this graph.

Note that the input phylogenetic graph is always connected, and a phylogenetic tree for it is guaranteed to exist.

Input

The first line contains an integer $N$ ($2 \le N \le 5000$), the number of vertices in the phylogenetic graph.

The vertices are numbered from $1$ to $N$.

The second line contains an integer $M$ ($1 \le M \le 1000000$), the number of edges in the phylogenetic graph.

Each of the next $M$ lines contains two integers $v,w$ ($1 \le v,w \le N$), the endpoints of an edge in the phylogenetic graph.

Output

On the first line, print the number $S$ of edges in the phylogenetic tree.

On each of the next $S$ lines, print the endpoint numbers $v$ and $w$ of an edge, separated by one space.

The tree edges may be printed in any order.

However, node numbers $1$ through $N$ must be assigned to the leaf nodes.

Furthermore, each vertex of the input phylogenetic graph and its corresponding leaf node in the phylogenetic tree must have the same number.

The remaining internal nodes may be numbered arbitrarily from $N+1$ through $S+1$. If more than one phylogenetic tree exists, find and print any one of them.

Examples

Input 1

6
7
1 2
2 3
3 1
3 4
3 5
5 6
6 3

Output 1

9
1 7
2 7
3 9
4 8
5 10
6 10
7 9
8 9
9 10

Scoring: 100 points if all tests pass, otherwise 0.