CF1559D2.Mocha and Diana (Hard Version)

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.

这是该问题的困难版本。两个版本的唯一区别在于对 $n$ 的约束条件。只有当该问题的所有版本均被解决时，才允许进行 hack。

森林是指无环的无向图（不一定是连通的）。

在浙江，Mocha 和 Diana 是朋友。她们各自拥有一个节点编号为 $1$ 到 $n$ 的森林。她们希望向各自的森林中添加若干条边，使得：

• 添加边之后，她们各自的图仍均为森林；
• 她们添加完全相同的边。即：若边 $(u, v)$ 被添加到 Mocha 的森林中，则边 $(u, v)$ 也必须被添加到 Diana 的森林中，反之亦然。

Mocha 和 Diana 想知道：她们最多能添加多少条边？以及具体应添加哪些边？

The first line contains three integers $n$, $m_1$ and $m_2$ ($1 \le n \le 10^5$, $0 \le m_1, m_2 \lt 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.

第一行包含三个整数 $n$、$m_1$ 和 $m_2$（$1 \le n \le 10^5$，$0 \le m_1, m_2 \lt n$），分别表示节点数量、Mocha 的森林中初始边的数量以及 Diana 的森林中初始边的数量。

接下来的 $m_1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示 Mocha 的森林中的边。

再接下来的 $m_2$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示 Diana 的森林中的边。

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.

第一行仅包含一个整数 $h$，表示 Mocha 和 Diana 最多可以添加的边数。

接下来的 $h$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，且 $u \neq v$），表示每次添加的边。

若存在多个正确答案，输出任意一个即可。

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

在第一个例子中，我们无法添加任何边。

在第二个例子中，初始的森林如下所示。

我们可以添加一条边 $(2, 4)$。