题目描述

伯利兰是一个拥有高度发达道路系统的国家。伯利兰共有 $n$ 个城市，每对城市之间恰好有一条双向通行的道路。

为了节约电力，伯利兰只照亮了 $m_1$ 条道路，其中第 $i$ 条道路连接城市 $v_i$ 和 $u_i$。出于安全考虑，伯利兰禁止在未照明的道路上通行。

在一个平行宇宙中，有一个类似的国度——黑利兰，也由 $n$ 个城市组成。黑利兰同样每对城市之间也恰好有一条道路。两国的区别仅在于电力节约政策：黑利兰照亮了 $m_2$ 条道路，其中第 $i$ 条道路连接城市 $a_i$ 和 $b_i$。已知在黑利兰可以通过仅使用照明的道路从任意城市到达任意其他城市。

你掌握了一种秘密咒语，可以选择任意两个不同的城市 $x$ 和 $y$，并在两个宇宙中同时改变城市 $x$ 和 $y$ 之间道路的照明状态。也就是说，在每个宇宙中，如果这条道路未被照明，则它将被照明；如果已被照明，则它将不再被照明。

你希望使用这种咒语不超过 $n$ 次，使得在伯利兰可以通过仅使用照明的道路从任意城市到达任意其他城市。同时，在每次使用咒语后，黑利兰必须保持连通性，即不存在两个城市之间无法通过照明道路到达。

请确定是否可以实现这一目标，如果可以，找到一种合适的咒语使用序列。

输入格式

每个测试点包含多组输入数据。第一行包含两个整数 $t$ 和 $g$ $(1 \leq t \leq 60000, 0 \leq g \leq 10)$，分别表示输入数据组数和子任务编号。接下来是各组数据的描述。

每组数据的第一行包含三个整数 $n, m_1, m_2$ $(3 \leq n \leq 300000, 0 \leq m_1, m_2 \leq 300000, m_1, m_2 \leq \frac{n(n-1)}{2})$，分别表示城市数量、伯利兰中照明的道路数量和黑利兰中照明的道路数量。

接下来的 $m_1$ 行描述伯利兰中照明的道路。第 $i$ 行包含两个整数 $v_i$ 和 $u_i$ $(1 \leq v_i, u_i \leq n)$，表示第 $i$ 条照明道路连接的城市编号。保证所有道路各不相同。

接下来的 $m_2$ 行描述黑利兰中照明的道路。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ $(1 \leq a_i, b_i \leq n)$，表示第 $i$ 条照明道路连接的城市编号。保证所有道路各不相同，并且在黑利兰中可以通过照明道路从任意城市到达任意其他城市。

设 $N, M_1, M_2$ 分别为所有数据组中 $n, m_1, m_2$ 的总和。保证 $N, M_1, M_2 \leq 300000$。

输出格式

对于每组输入数据，如果不存在满足条件的咒语序列，则输出 No。

否则，输出 Yes。在第二行输出一个整数 $k$ $(0 \leq k \leq n)$，表示你使用的咒语次数。

接下来输出 $k$ 行。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ $(1 \leq x_i, y_i \leq n, x_i \neq y_i)$，表示第 $i$ 次咒语应用的城市编号。注意，每次使用咒语后，黑利兰必须保持连通性。

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

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。