Mocha and Diana (Hard Version)

题意翻译

### 题目描述 给你两棵森林，节点数均为 $n$。 允许你进行加边操作，但是有两个要求： - 如果在第一个森林加一条 $(u,v)$ 的边，第二个森林也要进行同样的操作。反之同理。 - 加边后两个森林依旧是森林。（一棵树也是森林） 求最多能加几条边，并输出加边方案。 ### 输入格式 第一行三个整数 $n,m_1,m_2$（ $1 \le n \le 10^5,0 \le m_1,m_2 < n$ ），分别表示结点数，第一个森林的边数，第二个森林的边数。 接下来 $m_1$ 行，每行两个整数 $u,v$ ( $1 \le u,v \le n, u \ne v$ )，用来描述第一个森林。 接下来 $m_2$ 行，每行两个整数 $u,v$ ( $1 \le u,v \le n, u \ne v$ )，用来描述第二个森林。 ### 输出格式 第一行一个整数表示最多加边数。 接下来每行两个整数 $u,v$ 表示所加的边。

题目描述

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) $ .