P13506 [OOI 2024] Parallel Universes

Berlandia 是一个拥有高度发达公路系统的国家。该国共有 $n$ 个城市，每对城市之间恰好有一条公路，且可以双向通行。 为了节约用电，Berlandia 仅有 $m_1$ 条公路被照明，第 $i$ 条照明公路连接城市 $v_i$ 和 $u_i$。出于安全考虑，Berlandia 禁止在未照明公路上通行。 在一个平行宇宙中，有一个类似的国家 Cherlandia，也有 $n$ 个城市，每对城市之间也恰好有一条公路。两国唯一的区别在于节能方式：Cherlandia 有 $m_2$ 条照明公路，第 $i$ 条照明公路连接城市 $a_i$ 和 $b_i$。已知在 Cherlandia，任意两座城市之间都可以仅通过照明公路到达。 你拥有一个秘密法术，可以选择任意两个不同的城市 $x$ 和 $y$，并改变这两国之间 $x$ 和 $y$ 所连公路的照明状态。即：在每个国家中，如果这条公路原本未被照明，则变为照明；若原本已照明，则变为未照明。 你希望最多使用 $n$ 次法术，使得 Berlandia 也能实现任意两城市之间仅通过照明公路互达。同时，每次施法后，Cherlandia 必须始终保持**连通**，即不存在两座城市之间无法通过照明公路到达的情况。 请判断能否做到上述目标。如果可以，请给出一种符合要求的施法序列。

每个测试包含若干组数据。第一行包含两个整数 $t$ 和 $g$（$1 \le t \le 60\,000$，$0 \le g \le 10$），表示测试数据组数和测试组编号。接下来是每组测试数据的描述。 每组测试数据的第一行包含三个整数 $n$、$m_1$、$m_2$（$3 \le n \le 300\,000$，$0 \le m_1, m_2 \le 300\,000$，$m_1, m_2 \le \frac{n(n-1)}{2}$），分别表示城市数、Berlandia 照明公路数、Cherlandia 照明公路数。 接下来的 $m_1$ 行，每行两个整数 $v_i$、$u_i$（$1 \le v_i, u_i \le n$），表示 Berlandia 的一条照明公路。保证所有公路互不重复。 再接下来 $m_2$ 行，每行两个整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$），表示 Cherlandia 的一条照明公路。保证所有公路互不重复，且 Cherlandia 的照明公路网络是连通的。 设 $N$、$M_1$、$M_2$ 分别为本组所有数据中 $n$、$m_1$、$m_2$ 的和，保证 $N, M_1, M_2 \le 300\,000$。

对于每组测试数据，若不存在满足条件的施法序列，输出 `No`（不带引号）。 否则，输出 `Yes`。第二行输出一个整数 $k$（$0 \le k \le n$），表示你使用的法术次数。 随后 $k$ 行，每行两个整数 $x_i$、$y_i$（$1 \le x_i, y_i \le n$，$x_i \neq y_i$），表示第 $i$ 次施法作用的城市对。注意每次施法后，Cherlandia 必须保持连通。

在第一个数据组中，不存在合法的施法序列，因此输出 `No`。 在第二组数据中，初始照明公路结构如下： :::align{center}  ::: 对城市 $2$ 和 $4$ 施法后，这条公路在两国中都变为照明。操作后结构如下： :::align{center}  ::: 此时 Berlandia 已连通，方案合法。 在第三组数据中，先对 $1$ 和 $2$ 施法，此路在 Berlandia 变为未照明，在 Cherlandia 变为照明。再对 $2$ 和 $4$ 施法，两国结构如下： :::align{center}  ::: :::align{center}  ::: ### 计分方式 本题共十组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。**Offline-evaluation** 表示该组结果仅在赛后可见。 | 组别 | 分值 | 额外约束 | 依赖组 | 备注 | |:-----:|:------:|:----------------------:|:---------------:|:-------:| | 0 | 0 | -- | -- | 样例。 | | 1 | 9 | $N, M_1, M_2 \le 3000$，$n \le 5$ | -- | | | 2 | 7 | $N, M_1, M_2 \le 3000$，$m_2 = \frac{n(n - 1)}{2}$ | -- | | | 3 | 10 | $N, M_1, M_2 \le 3000$，Berlandia 恰好有两个连通块$^{[1]}$ | -- | | | 4 | 11 | $N, M_1, M_2 \le 3000$，Berlandia 无孤立城市$^{[2]}$ | -- | | | 5 | 15 | $N, M_1, M_2 \le 3000$，$m_2 = n - 1$，$a_i = 1, b_i = i + 1$ 对所有 $1 \le i \le n - 1$ | -- | | | 6 | 8 | $N, M_1, M_2 \le 3000$，$m_2 = n - 1$ | 5 | | | 7 | 12 | $N, M_1, M_2 \le 3000$，两国 $1-2$ 公路均照明 | -- | | | 8 | 6 | $N, M_1, M_2 \le 3000$ | 0 -- 7 | | | 9 | 8 | --，$m_2 = n - 1, a_i = i, b_i = i+1$ 对所有 $1 \le i \le n-1$ | -- | | | 10 | 14 | -- | 0 -- 9 | **Offline-evaluation.** | $^{[1]}$ **连通块**：任意两城市之间仅通过照明公路可达的集合。 $^{[2]}$ **孤立城市**：没有任何照明公路与之相连的城市。 翻译由 ChatGPT-4.1 完成。