7565: [CSES Problem Set] Building Roads
[Creator : ]
Description
Byteland has $n$ cities, and $m$ roads between them. The goal is to construct new roads so that there is a route between any two cities.
Your task is to find out the minimum number of roads required, and also determine which roads should be built.
Your task is to find out the minimum number of roads required, and also determine which roads should be built.
Input
The first input line has two integers $n$ and $m$: the number of cities and roads. The cities are numbered $1,2,\dots,n$.
After that, there are $m$ lines describing the roads. Each line has two integers $a$ and $b$: there is a road between those cities.
A road always connects two different cities, and there is at most one road between any two cities.
After that, there are $m$ lines describing the roads. Each line has two integers $a$ and $b$: there is a road between those cities.
A road always connects two different cities, and there is at most one road between any two cities.
Output
First print an integer $k$: the number of required roads.
Then, print $k$ lines that describe the new roads. You can print any valid solution.
Then, print $k$ lines that describe the new roads. You can print any valid solution.
Constraints
$1≤n≤10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
Sample 1 Input
4 2
1 2
3 4
Sample 1 Output
1
2 3