P16613 [Algo Beat 008 & WWOI R3] Tree Reconfiguration

Please note that if your program gets MLE, TLE, OLE, or RE, you will not obtain 40% of the score even if your Yes/No judgement is correct.

Murasame-chan gives you a tree with $n$ vertices, two sets $S$ and $T$ of size $k$, and an integer $D$. It is guaranteed that all elements in $S$ are distinct, and all elements in $T$ are distinct. Initially, all vertices $i$ such that $i \in S$ are marked, and all other vertices are unmarked. You may perform the following operation any number of times, possibly zero, until all vertices $i$ such that $i \in T$ are marked: - Choose a currently marked vertex $u$ and a currently unmarked vertex $v$ adjacent to $u$. The distance from $v$ to every currently marked vertex must be at most $D$. - Then unmark $u$ and mark $v$. Murasame-chan asks whether there exists a valid sequence of operations to achieve the goal. Since she is very cute, if such a sequence exists, you need to output it. **You must ensure that the length of the operation sequence does not exceed $\bm{10^6}$.** It can be proven that under the constraints of this problem, if a valid sequence of operations exists, then there is always one of length at most $10^6$. Specifically, if your Yes/No judgement is correct but your constructed sequence is invalid, you can still obtain 40% of the score for the corresponding test case. Please note that your output must be correctly formatted to obtain these points. If you only want to obtain these points, then when you determine that a solution exists, you may output a correctly formatted but not necessarily valid sequence, for example, $c=0$.

The first line contains three integers $n$, $k$, and $D$, denoting the number of vertices in the tree, the size of the sets, and the distance limit, respectively. Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \leq u, v \leq n$), denoting an edge between vertices $u$ and $v$. The next line contains $k$ distinct integers, denoting the set $S$. The next line contains $k$ distinct integers, denoting the set $T$. **It is guaranteed that the maximum distance between any two vertices in $\bm{S}$ is at most $\bm{D}$, and the maximum distance between any two vertices in $\bm{T}$ is at most $\bm{D}$.**

If a solution exists: - Print `Yes` on the first line. - On the second line, print an integer $c$, denoting the length of your operation sequence. You must ensure that $0 \leq c \leq 10^6$. - Then print $c$ lines. Each line should contain two integers $u$ and $v$, denoting an operation: unmark $u$ and mark $v$. You must ensure that every operation is valid. Any operation sequence satisfying the conditions will be accepted. If no solution exists: - Print a single string `No` on one line. The special judge is case-insensitive, that is, you may print `Yes` and `No` in any case, such as `yes`, `YES`, `yEs`, `NO`, or `nO`.

### Explanation for Sample 2 See the image below. The orange vertices represent the marked vertices that move during the operation, the blue vertices represent the marked vertices that do not move during the operation, and the arrows represent the direction of movement. :::info[Image]  ::: **Note: The outputs for the first two samples are not unique.** ### Constraints **This problem uses bundled testing.** For all test cases, it is guaranteed that $1 \leq n \leq 2000$, $2 \leq k \leq n$, and $1 \leq D \leq n$. ::cute-table{tuack} | Subtask | Additional Constraints | Score | | :-: | :-: | :-: | | 1 | $S=T$ | 5 | | 2 | $D=1$ | 5 | | 3 | $n \leq 12$ | 10 | | 4 | The tree is a single chain | 10 | | 5 | $k=2$ | 15 | | 6 | $D \geq$ diameter of the tree | 15 | | 7 | No additional constraints | 40 | Specifically, Subtask 7 depends on all previous subtasks.