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.

제한

힌트