405013: GYM101741 C Cover the Paths

You are given an undirected unweighted tree consisting of n vertices labeled by integers 1, 2, ..., 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 ≤ i ≤ 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 ≤ n ≤ 10⁵).

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 ≤ u_i, v_i ≤ n, u_i ≠ v_i). It is guaranteed that the given edges form a tree.

The next line contains an integer m, the number of paths (1 ≤ m ≤ 10⁵).

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 ≤ a_i, b_i ≤ 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.

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

1
2 

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

3
6 3 1