33450번 - Twinning Totem 스페셜 저지다국어

문제

"Ori, this is a Map Stone, one of the many ancient markers created to chart the forest of Nibel as it grew."

The Map Stone that Ori meets today is different from the others. The totem has two sides, and each side has $n$ hollows with $m$ scratches. Each scratch connects two hollows, and the hollows and the scratches on the two sides are the same. Each hollow can pass through the stone so that, if we put something on one side, we could also see it on the other side. However, the scratches are the same but cannot pass through, so we can put different things on two sides for each scratch.

Ori puts one Life Cell into hollow $u$ and $n - 1$ Energy Cells into the other $n - 1$ hollows. Now, on each side, Ori needs to select $n - 1$ scratches and inject light to them to form a spanning tree rooted in $u$. The two resulting trees should have the following property: for each Energy Cell, if it flows its energy to the Life Cell along light scratches on one side, and then flows back along the light scratches on the other side, no other Energy Cell will be passed twice.

Could Ori find two trees with the required properties?

입력

The first line contains two integers $n$ and $m$ (3ドル \le n \le 10^5,ドル $n - 1 \le m \le \min(2 \cdot 10^5,ドル $\frac{n(n - 1)}{2})$) denoting the number of hollows and the number of scratches of the totem $G,ドル respectively.

For the next $m$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ (1ドル \le x_i, y_i \le n$) denoting a scratch connecting hollow $x_i$ and hollow $y_i$.

The next line contains an integer $T$ (1ドル \le T \le 10^5$) denoting the number of Ori's attempts.

For the next $T$ lines, the $i$-th line contains an integer $u_i$ (1ドル \le u_i \le n$) denoting the hollow where Ori puts the Life Cell in the $i$-th attempt.

It is guaranteed that $G$ is a connected graph without self-loops or multiple edges, and that $n \cdot T \le 10^5$.

출력

For each attempt of Ori, if no solution exists, output "No" (without quotes) on the first line.

Otherwise, output "Yes" (without quotes) on the first line. Then, output 2ドル(n - 1)$ lines to describe the two spanning trees.

For the first $n - 1$ of these lines, the $i$-th line must contain two integers $x_i$ and $y_i$ (1ドル \le x_i, y_i \le n$) separated by a space, denoting a selected scratch connecting $x_i$ and $y_i$. The $n - 1$ scratches must form the first spanning tree of $G$.

The next $n - 1$ lines must describe the second spanning tree of $G$ in the same format.

Your answer will be accepted only when the two trees you output are valid spanning trees of $G$ and meet the requirements in the problem description: for any $v \in V$ such that $v \ne u,ドル the two simple paths from $u$ to $v$ in the two trees have no common nodes except their endpoints $u$ and $v$.

제한

노트

For the first example:

• For hollow 2ドル,ドル the paths in the two trees are $P_1 = \{2, 1\}$ and $P_2 = \{2, 3, 4, 1\}$.
• For hollow 3ドル,ドル the paths in the two trees are $P_1 = \{3, 2, 1\}$ and $P_2 = \{3, 4, 1\}$.
• For hollow 4ドル,ドル the paths in the two trees are $P_1 = \{4, 3, 2, 1\}$ and $P_2 = \{4, 1\}$.