Maximum Oddity

Everything seems a bit odd these days! To embrace the oddness, we present you an odd challenge!.
You are given an undirected graph $G$ with $N$ vertices and $M$ edges. The graph is not necessarily connected.
Your task is to construct a spanning subgraph $H$ of $G$ such that the number of vertices with odd degree in $H$ is maximized.

Write a program that selects a subset of edges from $G$ (possibly all or none) to delete, such that the resulting graph $H$ spans all $N$ vertices and has the maximum possible number of vertices with odd degree.

Input data

The first line of the input contains $N$ and $M$, the number of vertices and the number of edges in $G$.

The next $M$ lines each contain a pair of integers $U_i, V_i$, describing the edges in the graph.

Output data

The first line of the output contains two integers:

• $X$, the maximum number of vertices with an odd degree in a spanning subgraph $H$.
• $K$: the number of edges to be deleted from $G$ to obtain $H$.

The next $K$ lines each contain a pair of integers: the endpoints of an edge (in arbitrary order) which you choose to delete.

If there are multiple solutions, you may print any correct one.

Constraints and clarifications

• $1 \le N \le 100\,000$.
• $1 \le M \le 200\,000$.
• $1 \le U_i, V_i \le N$ and $U_i \neq V_i$ for each $i=0\ldots M - 1$.
• There is at most one edge between any pair of vertices.
• A spanning subgraph of $G$ is a subgraph that includes all $N$ vertices of $G$ but may include only a subset of the edges. The resulting subgraph $H$ can have cycles, multiple components, or isolated vertices.

Example 1

stdin

4 3
1 2
2 4
4 1

stdout

2
1
4 2

Explanation

In the first sample case, the graph in the input is shown in the figure below.

The maximum number of odd vertices in a spanning subgraph $H$ is $2$. We can remove any edge, or any pair of two edges to obtain such a subgraph.

Example 2

stdin

6 9
1 2
2 3
3 1
1 4
2 5
3 6
4 5
5 6
6 4

stdout

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