Sky Cities

In the year 4000 the surface of the Earth is ruined, so people float islands in the air and live in cities built on them. An island carries only so much weight, so every city is small, and bridges between the cities let anyone travel from any city to any other. The picture below shows six sky cities, numbered 1 to 6, joined by bridges.

More than one bridge can join the same two cities. In the picture, two different bridges join city 2 and city 4.

A natural disaster sometimes tears one bridge down. If the bridge between city 5 and city 6 goes down, nobody can leave city 6. If instead the bridge between city 1 and city 3 goes down, travel between every pair of cities still works.

So the plan is to build extra bridges until travel between every pair of cities survives the loss of any single bridge. For the map above, one extra bridge between city 3 and city 6 is enough, as the next picture shows. A bridge from city 6 to some other city also works.

Given the sky cities and the bridges that stand now, write a program that finds the smallest number of extra bridges needed so that travel between every pair of cities survives the loss of any single bridge, and finds where to build them. The length of a bridge does not matter.

The first line holds the number of cities $N$ and the number of bridges $M$, where $3 \le N \le 100{,}000$ and $N-1 \le M \le 200{,}000$. Each of the next $M$ lines holds the two cities $C_1$ and $C_2$ that one bridge joins directly, where $1 \le C_1, C_2 \le N$. The bridges given allow travel between every pair of cities.

Print the smallest number of extra bridges $R$ on the first line. On each of the next $R$ lines print the two cities $D_1$ and $D_2$ that one new bridge joins directly, smaller number first.

Several sets of bridges can reach the minimum, so print only the one this rule fixes.

1. Call a bridge critical when removing it leaves some pair of cities unable to reach each other. Remove every critical bridge at once, which splits the cities into groups. Each group is a block, and the number of a block is the smallest city number in it.
2. Take the blocks as vertices and the critical bridges as edges. The result is a tree. Root it at the block that holds city 1 and run a depth first search that visits the children of a block in increasing order of block number. In the order the search visits them, list the blocks that have exactly one neighbor in the tree as $l_1, l_2, \dots, l_L$.
3. Let $k = \lceil L/2 \rceil$. For $i = 1, 2, \dots, L-k$ in that order, print one line per $i$ holding a bridge between the number of $l_i$ and the number of $l_{i+k}$. If $L$ is odd, print one more bridge on the last line, between the number of $l_k$ and the number of $l_1$.
4. If no bridge is critical, then $R = 0$ and nothing follows the first line.