Redrawn graph
本题没有可用的提交语言。
Description
During a very boring math lesson, Masha drew an undirected graph in her notebook with $n$ vertices and $m$ edges. The vertices of the graph were numbered from $1$ to $n$.
After the lesson, she went on a break, and when she returned, she found that the graph seemed to have changed!
Masha's desk mate, Pasha, admitted that he had made some changes to the graph while Masha was away. Specifically, he performed the following operation: he took three distinct vertices of the graph, $a$, $b$, and $c$, and for each pair of vertices $(a, b)$, $(b, c)$, and $(a, c)$, he modified the corresponding edge: if it existed in the current graph, he removed it, and if it didn't exist, he added it.
He performed this operation not just once, but several times (possibly zero or one), each time choosing $a$, $b$, and $c$ again.
Masha wants to verify her neighbor's words, so she asks you to find any sequence of Pasha's actions that could have transformed the original graph into the one Masha has in her notebook originally.
The first line contains three numbers, $n$, $m$, and $k$ ($3 \le n \le 10^5$; $0 \le m, k \le 10^5$), which represent the number of vertices, the number of edges in the original graph, and the number of edges in the resulting graph, respectively.
Each of the next $m$ lines contains two numbers, $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \neq v_i$), indicating the vertices connected by the $i$-th edge in the original graph.
The following $k$ lines describe the resulting graph in the same format. It is guaranteed that both graphs do not contain loops or multiple edges.
If it is impossible to obtain the second graph from the first one using Pasha's actions, output «NO» in a single line.
Otherwise, output «YES» in the first line. In the next line, output the number of operations $t$ ($0 \le t \le 2\cdot 10^5$) that Pasha had to perform. In each of the next $t$ lines, output three numbers $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i, c_i \le n$, the numbers $a_i$, $b_i$, $c_i$ should be pairwise distinct), indicating the vertices that Pasha had to choose on the $i$-th step.
Note that you do not need to minimize the number of Pasha's actions, but it should not exceed $2\cdot 10^5$. It can be shown that if a solution exists, then there exists a solution consisting of no more than $2\cdot 10^5$ actions.
Input
The first line contains three numbers, $n$, $m$, and $k$ ($3 \le n \le 10^5$; $0 \le m, k \le 10^5$), which represent the number of vertices, the number of edges in the original graph, and the number of edges in the resulting graph, respectively.
Each of the next $m$ lines contains two numbers, $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \neq v_i$), indicating the vertices connected by the $i$-th edge in the original graph.
The following $k$ lines describe the resulting graph in the same format. It is guaranteed that both graphs do not contain loops or multiple edges.
Output
If it is impossible to obtain the second graph from the first one using Pasha's actions, output «NO» in a single line.
Otherwise, output «YES» in the first line. In the next line, output the number of operations $t$ ($0 \le t \le 2\cdot 10^5$) that Pasha had to perform. In each of the next $t$ lines, output three numbers $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i, c_i \le n$, the numbers $a_i$, $b_i$, $c_i$ should be pairwise distinct), indicating the vertices that Pasha had to choose on the $i$-th step.
Note that you do not need to minimize the number of Pasha's actions, but it should not exceed $2\cdot 10^5$. It can be shown that if a solution exists, then there exists a solution consisting of no more than $2\cdot 10^5$ actions.
3 0 3
1 2
2 3
3 1
4 3 3
1 2
2 3
3 4
1 3
4 2
2 3
3 1 1
1 2
2 3
YES
1
1 2 3
YES
2
1 3 4
1 2 4
NO