Wireless Instead of Fiber

A new kind of wireless communication with unbounded bandwidth has passed its tests, and it can replace the fiber network that no longer keeps up with traffic growth. You decide the layout of the replacement.

The existing network is a set of nodes that route messages, together with fiber links, each joining two different nodes. Between every pair of nodes there is at least one route along the fiber, and a pair of nodes may be joined by more than one link for bandwidth reasons.

The new network has no fiber. It has wireless links, each joining two nodes. Bandwidth is unbounded, but a wireless link is expensive, so the new network keeps everything connected with as few links as possible: between every pair of nodes there must be exactly one route along the wireless links. Each node was also built with a particular number of connections in mind. A node that ends up connected to a different number of links than it has today must be reorganized, and that costs money.

Design the new network so that exactly one path joins each pair of nodes and the number of nodes whose link count differs from the existing network is as small as possible.

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^4$, $1 \le m \le 10^5$), the number of nodes and the number of fiber links in the existing network. The nodes are numbered from $0$ to $n - 1$.

Each of the next $m$ lines contains two distinct integers $a_i$ and $b_i$, meaning that the $i$-th fiber link joins node $a_i$ and node $b_i$. For every pair of nodes there is at least one path of fiber links connecting them. A pair of nodes may be joined by more than one fiber link.

On the first line print the smallest number of nodes whose number of links has to change.

On the second line print the number of nodes, which equals the number in the input, and the number of wireless links. On each of the remaining lines print one wireless link as two node numbers with the smaller number first. Sort the links in ascending order, first by the smaller number and then by the larger one.

Many layouts reach the minimum, so print the one that this procedure builds. Let $d_v$ be the number of fiber links at node $v$ in the existing network, counting repeated links between the same pair separately.

1. Sort the nodes by $d_v$ ascending and break ties by the smaller node number. Read the sorted list from the front, keeping a running sum that starts at $0$. At each node add $d_v - 1$ to the running sum when the result stays at most $n - 2$, and stop at the first node that would push the running sum above $n - 2$. The nodes read before that stop are the preserved nodes.
2. Set $t_v = d_v$ for every preserved node and $t_v = 1$ for every other node. When at least one node is not preserved, add $2n - 2 - \sum_v t_v$ to $t_w$, where $w$ is the smallest-numbered node that is not preserved.
3. When $n = 2$, the single wireless link joins node $0$ and node $1$. Otherwise let $v_1 < v_2 < \dots < v_p$ be the nodes with $t_v \ge 2$, and let $u_1 < u_2 < \dots < u_L$ be the nodes with $t_v = 1$. Build the path $v_1 v_2, v_2 v_3, \dots, v_{p-1} v_p$. The free capacity of $v_i$ is $t_{v_i}$ minus the number of path links already at $v_i$. Attach $u_1, u_2, \dots, u_L$ in that order, each one to the first $v_i$ that still has free capacity, so the free capacity of $v_1$ is used up before $v_2$ takes a node.

Step 3 always places every $u_j$, and the number of wireless links is always $n - 1$.