Mocha and Diana (Hard Version)

2000ms

262144K

Description:

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

A forest is an undirected graph without cycles (not necessarily connected).

Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from $$$1$$$ to $$$n$$$, and they would like to add edges to their forests such that:

After adding edges, both of their graphs are still forests.
They add the same edges. That is, if an edge $$$(u, v)$$$ is added to Mocha's forest, then an edge $$$(u, v)$$$ is added to Diana's forest, and vice versa.

Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.

Input:

The first line contains three integers $$$n$$$, $$$m_1$$$ and $$$m_2$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le m_1, m_2 < n$$$) — the number of nodes and the number of initial edges in Mocha's forest and Diana's forest.

Each of the next $$$m_1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Mocha's forest.

Each of the next $$$m_2$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Diana's forest.

Output:

The first line contains only one integer $$$h$$$, the maximum number of edges Mocha and Diana can add.

Each of the next $$$h$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edge you add each time.

If there are multiple correct answers, you can print any one of them.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

1
2 4

Sample Input:

Sample Output:

Note:

In the first example, we cannot add any edge.

In the second example, the initial forests are as follows.

$\text{[math]}$

We can add an edge $$$(2, 4)$$$.

$\text{[math]}$

Informação

Provedor Codeforces

Código CF1559D2