P10731 [NOISG 2023 Qualification] Network

Duck Rui Yuan has $n$ servers and $n-1$ **bidirectional** data cables. The $i$-th cable connects $u_i$ and $v_i$ **in both directions**. It is guaranteed that for all $1 \le i \not = j \le n$, you can reach server $j$ from server $i$ through the cables, and vice versa. Rui Yuan also has $m$ applications running. The $j$-th application runs on two servers, $a_j$ and $b_j$. Initially, all servers are running. The $j$-th application can run if **both** of the following conditions hold: - Both $a_j$ and $b_j$ are running servers. - Between $a_j$ and $b_j$, there is a connection through data cables and **running servers**. Rui Yuan wants you to find the minimum number of servers that must be stopped so that all applications stop running.

The first line contains two integers $n,m$. The next $n-1$ lines each contain two integers $u_i,v_i$. The next $m$ lines each contain two integers $a_j,b_j$.

The first line contains an integer $x$, the minimum number of servers that must be stopped. The next $1$ line contains $x$ integers, the indices of the servers to be stopped. All $x$ integers must be distinct. You may output them in any order.

### Constraints |$\text{Subtask}$|Score|Special Property| |:-:|:-:|:-:| |$0$|$0$|Sample| |$1$|$4$|$a_i=b_i$| |$2$|$17$|$u_i=i,v_i=i+1$| |$3$|$14$|$n,m\le15$| |$4$|$29$|$n,m\le2000$| |$5$|$36$|None| For $100\%$ of the testdata, $1 \le n,m \le 200000, 1 \le u_i,v_i \le n, u_i\not = v_i, 1 \le a_j,b_j\le n$. Translated by ChatGPT 5