Trade Partner Expansion

In Anihc, there are \(n\) cities. Some pairs of cities have a direct trade agreement; if there is an agreement between city \(x\) and city \(y\), then they are trade partners. It is guaranteed that the \(n\) cities can be partitioned into at most two connected groups (i.e. connected components).

The government plans to build a new kind of urban relationship. They want to select two cities that are not currently direct trade partners and establish a direct trade agreement between them. This new connection must have the effect that the size of the largest connected group increases by at least \(1\) compared to before. In other words, if \(M\) is the size of the largest connected component in the original graph, then after adding the new connection the largest component must have size at least \(M+1\).

Your task is to determine all unordered pairs of cities \((a, b)\) (with \(a < b\)) such that if a new trade agreement is established between them, the condition on the connected group size is met.

Note: Cities are numbered from 1 to \(n\). Also, if the graph is already connected (i.e. only one connected group exists), then no such pair exists.

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) (\(2 \le n \le 10^5\)) is the number of cities and \(m\) is the number of existing trade agreements.

The following \(m\) lines each contain two integers \(x\) and \(y\) (\(1 \le x, y \le n,\ x \neq y\)), indicating that there is a trade agreement between city \(x\) and city \(y\). It is guaranteed that the resulting graph has at most two connected components.

outputFormat

First, output an integer \(k\) representing the number of valid pairs.

Then output \(k\) lines, each containing two integers \(a\) and \(b\) (with \(a < b\)), denoting that establishing a trade agreement between city \(a\) and city \(b\) will make the largest connected component increase in size by at least 1. The pairs should be listed in lexicographical order (first by \(a\), then by \(b\)).

sample

3 3
1 2
2 3
1 3

0