405306: GYM101879 C Promenade by the lake

The city of Porto will host the ICPC World Finals in 2019. One of the secret touristic spots in the city is the so-called "lake of the thousand bridges". Mr. Manoel Pontes (Pontes stands for "bridges" in Portuguese; this is amazingly his real name$$$\ldots$$$) built this wonder in the lake with a lifetime of hard work. The lake has many small islands. Mr. Manoel built small wooden bridges connecting the islands. In some cases, there are multiple bridges connecting some pairs of islands. Visitors enjoy themselves while promenading through the bridges and small islands. Besides, by walking through the bridges the visitors can go from one island to any other island.

Mr. Manoel wants to enhance this touristic attraction to get even more visitors. One of this ideas is to organize visitors games. He plans to have the following challenge: is it possible to start to walk from outside the lake, pass through all the bridges without repetition, and go back to the starting point (that is, back out of the lake)?

Before creating the attraction, he himself tried it over and over but could not find out if this was possible. To make the challenge even more interesting, Mr. Manoel will allow adding some bridges between some islands. He wants to know if, by adding some of these bridges, the walk he wants the game to have becomes possible. Your task in this problem is to decide if it is possible to choose some (possibly none) of these bridges that, when added, allow people to walk as described.

The first line has three integers $$$N$$$, $$$M$$$ and $$$K$$$, where $$$N$$$ is the number of islands, $$$M$$$ is the number of already built bridges and $$$K$$$ is the number of bridges that is possible to add. The islands are represented by distinct integers from $$$1$$$ to $$$N$$$. Each one of the following $$$M+K$$$ lines describes a bridge. Each one of them has two integers, $$$a$$$ and $$$b$$$, that represent the existence or possibility of adding a bridge between islands $$$a$$$ and $$$b$$$. The first $$$M$$$ lines describe bridges that already exist and the next $$$K$$$ lines describe bridges that you may add.

Constraints

• $$$1 \leq N \leq 3 \cdot 10^5$$$
• $$$0 \leq M, K \leq 3 \cdot 10^5$$$
• $$$1 \leq a < b \leq N$$$
• You may assume that we can go from one island to any other island by using only the bridges already built.

In the first line print "YES" (without the quotes), if such a walk is possible or "NO" otherwise. If there is a solution, print in the second line an integer $$$R$$$, $$$0 \leq R \leq K$$$ that is the number of bridges that need to be added. Next print $$$R$$$ lines, each one with two integers, the islands that are connected by this bridge, in any order. If there are multiple solutions, any one will be accepted.

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

YES
1
1 4

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

NO