CF1559D2.Mocha and Diana (Hard Version)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

输入格式

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.

输出格式

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.

输入输出样例

输入#1
```
3 2 2
1 2
2 3
1 2
1 3
```
输出#1
```
0
```
输入#2
```
5 3 2
5 4
2 1
4 3
4 3
1 4
```
输出#2
```
1
2 4
```
输入#3
```
8 1 2
1 7
2 6
1 5
```
输出#3
```
5
5 2
2 3
3 4
4 7
6 8
```

说明/提示

In the first example, we cannot add any edge.

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

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

首页