시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1 1 1 100.000%

문제

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.

예제 입력 1

4
1 2
2 3
2 4
2
1 2
4 2

예제 출력 1

1
2

예제 입력 2

6
1 2
2 3
3 4
5 6
5 2
5
2 1
6 6
1 4
3 4
4 1

예제 출력 2

3
6 3 1