题目描述

Berlandia --- a country with a highly developed road system. There are a total of $n$ cities in Berlandia, and there is exactly one road between each pair of cities, accessible for travel in both directions.

For the purpose of saving electricity, only $m_1$ roads are illuminated in Berlandia, the $i$-th of which connects cities $v_i$ and $u_i$. For safety reasons, it is forbidden to travel on unlit roads in Berlandia.

In a parallel universe, there is a similar country called Cherlandia, consisting of $n$ cities. There is also exactly one road between each pair of cities in Cherlandia. The countries differ only in their electricity economy: in Cherlandia, $m_2$ roads are illuminated, the $i$-th of which connects cities $a_i$ and $b_i$. It is known that in Cherlandia, it is possible to travel from any city to any other using only illuminated roads.

You possess a secret spell that allows you to choose any two different cities $x$ and $y$ and change the illumination on the road between cities $x$ and $y$ in both universes. That is, in each universe, if the road was not illuminated, it becomes illuminated, and vice versa.

You want to use this spell no more than $n$ times in order to make it possible to travel from any city to any other in Berlandia using only illuminated roads. At the same time, after each spell is cast, Cherlandia must remain $\textit{connected}$, that is, there should not exist two cities between which it is impossible to travel on illuminated roads.

Determine if this can be achieved, and if so, find a suitable sequence of spells.

输入格式

Each test consists of several sets of input data. The first line contains two integers $t$ and $g$ ($1 \le t \le 60\,000$, $0 \le g \le 10$) --- the number of sets of input data and the test group number. This is followed by descriptions of the sets of input data.

The first line of each set of input data description contains three integers $n$, $m_1$, and $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}$) --- the number of cities, the number of illuminated roads in Berlandia, and the number of illuminated roads in Cherlandia.

The next $m_1$ lines contain descriptions of illuminated roads in Berlandia. The $i$-th line contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$) --- the numbers of cities connected by the $i$-th illuminated road. It is guaranteed that all roads are distinct.

The next $m_2$ lines contain descriptions of illuminated roads in Cherlandia. The $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) --- the numbers of cities connected by the $i$-th illuminated road. It is guaranteed that all roads are distinct, and that in Cherlandia, there exists a path consisting only of illuminated roads between any two cities.

Let $N$, $M_1$, and $M_2$ be the sum of $n$, $m_1$, and $m_2$ for all sets of input data in one test. It is guaranteed that $N, M_1, M_2 \le 300\,000$.

输出格式

For each set of input data, output $\tt{No}$ (without quotes) if there is no sequence of spells that satisfies all conditions.

Otherwise, output $\tt{Yes}$. On the second line, output an integer $k$ ($0 \le k \le n$) --- the number of spells you have used.

Then output $k$ lines. In the $i$-th line, output two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \neq y_i$) --- the numbers of cities to which the $i$-th spell is applied. Note that after each spell is cast, Cherlandia must remain $\textit{connected}$.

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

提示

Note

In the first set of input data, there is no suitable sequence of spells, so the answer is $\tt{No}$.

In the second set of input data, the illuminated roads initially have the following structure:

:::align{center} :::

After casting a spell on cities $2$ and $4$ in both Berlandia and Cherlandia, this road becomes illuminated, as it was unlit in both countries. After this operation, the countries will have the following structure:

:::align{center} :::

After this operation, it is possible to travel from any city to any other in Berlandia, so this sequence of spells is correct.

In the third set of input data, after casting a spell on cities $1$ and $2$, the road between these two cities in Berlandia ceases to be illuminated, as it was illuminated before. In Cherlandia, on the contrary, the road becomes illuminated. After this operation, the countries will have the following structure:

:::align{center} :::

After casting a spell on cities $2$ and $4$, the countries will have the following structure:

:::align{center} :::

Scoring

The tests for this problem consist of ten groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed. Please note that passing the example tests is not required for some groups. $\textbf{Offline-evaluation}$ means that the results of testing your solution on this group will only be available after the end of the competition.

Group	Points	Additional constraints	Required Groups	Comment
0		--	--	Examples.
1	9	$N, M_1, M_2 \le 3000$		$n \le 5$
2	7			$m_2 = \frac{n(n - 1)}{2}$
3	10			Berlandia consists of two connected components$^{[1]}$
4	11			There are no isolated$^{[2]}$ cities in Berlandia
5	15			$m_2 = n - 1$, $a_i = 1$ and $b_i = i + 1$ for all $1 \le i \le n - 1$
6	8		5	$m_2 = n - 1$
7	12		--	In both countries, the road between cities $1$ and $2$ is illuminated
8	6		0 -- 7
9	8	--	--	$m_2 = n - 1$, $a_i = i$ and $b_i = i + 1$ for all $1 \le i \le n - 1$
10	14		0 -- 9	Offline-evaluation.

$^{[1]}$ Connected component — a set of cities such that there exists a path consisting only of illuminated roads between any pair of them.

$^{[2]}$ A city is called isolated if there is no illuminated road connecting it to any other city.