P3731 [HAOI2017] New-type Urbanization

There are $n$ cities in Anihc. Some cities have trade cooperation relations: if there is a trade agreement between city $x$ and city $y$, then city $x$ and city $y$ are a pair of trade partners (note: $(x,y)$ and $(y,x)$ denote the same pair of cities). To implement new-type urbanization, integrate urban and rural development, and leverage the radiation and driving role of city clusters, the country decides to plan new city relations. A set of cities can be called a city cluster if every pair among them are trade partners. Since Anihc has long attached importance to building city relations, it is guaranteed that, under the currently existing trade cooperation relations, the $n$ cities can be partitioned into at most two city clusters. To build new city relations, Anihc wants to select two cities that are not yet trade partners, make them trade partners, and requires that after these two cities become trade partners, the size of the largest city cluster is at least $1$ larger than the size of the largest city cluster before they became partners. Anihc needs to discuss expanding the construction of new city relations at the next meeting, so you are asked to find all pairs of cities between which establishing a trade partnership would satisfy this condition, i.e., the size of the largest city cluster after establishing the partnership is at least $1$ greater than before.

The first line contains $2$ integers $n, m$, the number of cities and the number of unordered city pairs that have not yet established a trade partnership. The next $m$ lines each contain $2$ integers $x, y$, indicating that cities $x$ and $y$ have not yet established a trade partnership.

Output one integer $\text{ans}$ on the first line, the number of qualifying city pairs. Then output $\text{ans}$ lines, each containing two integers, representing a pair of cities that can be chosen to establish a trade partnership. For a pair of cities $x, y$, output the smaller index first. Finally, sort the pairs in ascending lexicographic order.

Test point $1$: $n \le 16$. Test point $2$: $n \le 16$. Test points $3 \sim 5$: $n \le 100$. Test point $6$: $n \le 500$. Test points $7 \sim 10$: $n \le 10^4$. For all testdata, it is guaranteed that $n \le 10^4, 0 \le m \le \min(1.5 \times 10^5, \dfrac{n(n-1)}{2})$. It is guaranteed that there is no relation of the form $(x, x)$ in the input, and no pair of cities appears twice (no multiple edges, no self-loops). Translated by ChatGPT 5