← 返回题目列表

Codeforces · 1559/D2

D2. 摩卡和戴安娜(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。两个版本之间的唯一区别是对 $$$n$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

森林是一个没有环路(不一定相连)的无向图。

Mocha 和 Diana 是枝江的朋友,他们都有一个森林,节点编号从 $$$1$$$ 到 $$$n$$$,他们想向他们的森林添加边,这样:

- 添加边后,它们的两个图仍然是森林。
- 他们添加相同的边缘。也就是说,如果将边 $$$(u, v)$$$ 添加到 Mocha 的森林,则将边 $$$(u, v)$$$ 添加到 Diana 的森林,反之亦然。

Mocha 和 Diana 想知道他们可以添加的最大边数,以及要添加哪些边。

输入

第一行包含三个整数 $$$n$$$、$$$m_1$$$ 和 $$$m_2$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le m_1, m_2 < 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$$$) — 戴安娜森林中的边缘。

输出

第一行仅包含一个整数 $$$h$$$,Mocha 和 Diana 可以添加的最大边数。

接下来的 $$$h$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — 您每次添加的边。

如果有多个正确答案,您可以打印其中任意一个。

示例

输入 #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

注意

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

在第二个示例中,初始森林如下。

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