Reconstructing the Hidden Design

This is an interactive-style problem (simulated in an offline manner). You work at a toy design company where the toy consists of n push pins numbered from 1 to n protruding from a box. In the hidden design (called the 0^th scheme), some pairs of push pins are connected via wires, forming an undirected graph. The wires themselves are hidden from view. The only way to get information about the connections is by using a detector which, given any two distinct push pins i and j, tells you whether they are connected (directly or indirectly) in a particular design scheme.

You are allowed to simulate operations that, in an interactive setting, would let you query and generate new design schemes by adding a wire between two pins if they are not already connected in the current scheme. However, your ultimate goal is to produce any design scheme equivalent to the 0^th scheme. Two design schemes are said to be equivalent if, for every pair of pins, the detector would report the same connectivity result on both schemes.

In this offline version, the hidden design scheme is provided as input. Your task is to reconstruct a new design scheme (by outputting a series of wires) that preserves the connectivity of the given 0^th scheme. In other words, for any two pins i and j, they are connected in your output design if and only if they are connected in the input.

A straightforward way is to compute the spanning forest (i.e. a spanning tree for each connected component) of the input graph. Note that if a component consists of a single pin, no wire is needed. Your output scheme should list the wires that form this spanning forest. Such a spanning forest is equivalent to the original design scheme since it maintains exactly the same connectivity.

inputFormat

Input Format:

• The first line contains two integers n and m, where n (1 ≤ n ≤ 10⁵) is the number of push pins and m (0 ≤ m ≤ 10⁵) is the number of wires in the hidden design scheme.
• Each of the following m lines contains two integers u and v (1 ≤ u, v ≤ n and u ≠ v) representing a wire connecting push pin u and push pin v.

outputFormat

Output Format:

• On the first line, output an integer k, the number of wires in your reconstructed design scheme.
• Then output k lines, each line containing two integers representing a wire between two push pins.

The output must form a spanning forest of the input graph; that is, for every two pins i and j, they are connected in your output if and only if they are connected in the input.

sample

3 2
1 2
2 3

2
1 2
2 3