19326번 - Cover the Paths 스페셜 저지다국어

You are given an undirected unweighted tree consisting of $n$ vertices labeled by integers $1$, $2$, $\ldots$, $n$. A total of $m$ simple paths are chosen in this tree. Each path is described as a pair of its endpoints $(a_i, b_i)$.

Let $V$ be the set of all vertices of the tree. We say that subset $S$ of $V$ is good if for every $i$ such that $1 \le i \le m$, the simple path from $a_i$ to $b_i$ contains at least one vertex from $S$. We say that subset $T$ be the best subset if $T$ is a good subset and there is no good subset $X$ such that $|X| < |T|$.

You have to find the best subset of $V$.

The first line contains an integer $n$, the number of vertices in the tree ($1 \le n \le 10^5$).

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). It is guaranteed that the given edges form a tree.

The next line contains an integer $m$, the number of paths ($1 \le m \le 10^5$).

Each of the next $m$ lines describes a path in the tree. Path $i$ is denoted by two integers $a_i$ and $b_i$, the labels of the endpoints ($1 \le a_i, b_i \le n$). For some paths, it may be that $a_i = b_i$. It is not guaranteed that all paths are pairwise distinct.

On the first line, print the size of the best subset of $V$. On the second line, print the labels of vertices belonging to the best subset of $V$ in any order.

If there are several possible solutions, print any one of them.