Wireless Communication Network Design

A new type of unbounded‐bandwidth wireless communication has just been tested and is deemed a suitable replacement for the existing fiber‐based communications network. The current network consists of a set of nodes (which route messages) and fiber links connecting pairs of nodes – the network is connected (there is at least one path between every pair of nodes). For each node the number of fiber links incident to it is considered its original degree.

The new wireless network will have no fiber but will instead have wireless links connecting pairs of nodes. Such links have unbounded bandwidth but are expensive. Therefore, it is decided that the new network should use as few links as possible while still ensuring that there is exactly one path between any pair of nodes; that is, the wireless network will form a spanning tree. However, if in the new network a node is connected to a different number of links than it originally had, that node must be reorganized – a costly process.

Your task is to choose a spanning tree on the given nodes (using any pairwise wireless links) such that:

• The tree has exactly n − 1 links and there is exactly one path between any two nodes (i.e. it is connected and acyclic). In particular, the degrees t_i in the tree satisfy \( \sum_{i=1}^{n}t_i = 2(n-1) \) and for \(n\ge2\) every node has \(t_i\ge 1\).
• The number of nodes for which \(t_i \neq d_i\) (where \(d_i\) is the original degree) is minimized.

If there are several solutions with the minimum number of reorganizations, any one of them will be accepted.

inputFormat

The input begins with two integers \(n\) and \(m\) where \(n\) (1 \(\le\) n \(\le\) 10⁵) is the number of nodes and \(m\) is the number of fiber links in the original network. The nodes are numbered from 1 to \(n\). Following this are \(m\) lines, each containing two integers \(u\) and \(v\) (1 \(\le\) u, v \(\le\) n, u \(\neq\) v) which represent a fiber link between nodes \(u\) and \(v\>.

It is guaranteed that the original network is connected.

outputFormat

First, output an integer representing the minimum number of nodes that require reorganization (i.e. the number of nodes for which the new degree differs from the original degree). Then output exactly \(n-1\) lines each containing two integers \(u\) and \(v\) indicating that a wireless link is built between nodes \(u\) and \(v\).

If there are several solutions achieving the minimum reorganization cost, any one will be accepted.

sample

4 3
1 2
2 3
3 4

0
1 2
2 3
3 4