Description

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 必须始终保持连通，即不存在两座城市之间无法通过照明公路到达的情况。

请判断能否做到上述目标。如果可以，请给出一种符合要求的施法序列。

Input Format

每个测试包含若干组数据。第一行包含两个整数 $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$。

Output Format

对于每组测试数据，若不存在满足条件的施法序列，输出 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 必须保持连通。

3 0
3 0 3
1 2
2 3
1 3
4 2 3
1 2
3 4
1 3
1 4
2 3
4 3 3
1 2
2 3
1 3
1 4
2 4
3 4

No
Yes
1
2 4
Yes
2
1 2
4 2

Hint

在第一个数据组中，不存在合法的施法序列，因此输出 No。

在第二组数据中，初始照明公路结构如下：

:::align{center} :::

对城市 $2$ 和 $4$ 施法后，这条公路在两国中都变为照明。操作后结构如下：

:::align{center} :::

此时 Berlandia 已连通，方案合法。

在第三组数据中，先对 $1$ 和 $2$ 施法，此路在 Berlandia 变为未照明，在 Cherlandia 变为照明。再对 $2$ 和 $4$ 施法，两国结构如下：

:::align{center} :::

:::align{center} :::

计分方式

本题共十组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。Offline-evaluation 表示该组结果仅在赛后可见。

$^{[1]}$ 连通块：任意两城市之间仅通过照明公路可达的集合。

$^{[2]}$ 孤立城市：没有任何照明公路与之相连的城市。

翻译由 ChatGPT-4.1 完成。