thesis

Test Question

The lovely WrongAnswer is very fond of independent set problems. For his thesis defense in CTSC2017, he prepared a paper on independent sets.

One day, WrongAnswer decided he would use this paper to set a question. The question he eventually came up with was:

• Given a tree of \(n\) vertices \(T = (V, E)\) and an independent set \(I\), find the independent set whose lexicographical order is exactly \(k\) larger than \(I\).

WrongAnswer asks you to test this problem for him. Here are some definitions that may be useful:

• An independent set \(I\) is a subset of \(V\) satisfying the condition that any two vertices in \(I\) are not adjacent in the tree. In other words, there are no two vertices \(x, y \in I\) with \((x, y) \in E\).
• Suppose you have two vertex sets \(A, B\). Let the vertex indices in \(A\) be \(a_1, a_2, \ldots, a_{|A|}\) in ascending order; and similarly, let the indices in \(B\) be \(b_1, b_2, \ldots, b_{|B|}\) in ascending order. Then, \(A\) is lexicographically smaller than \(B\) if on the lowest \(i\) where \(a_i\) and \(b_i\) differ, \(a_i < b_i\).

If all independent sets of \(T\) were sorted lexicographically under these definitions, \(I\) would be the \(x^{th}\) set in the order. Output the \((x + k)^{th}\) set in the order, or the empty set if no such set exists.

Limits

\(1 \leq n \leq 10^6\)
\(1 \leq k \leq 10^{18}\)

Subtasks #	Score	Constraints
1	6	\(1 \leq n \leq 20\)
2	17	\(1 \leq n \leq 2000\) \(1 \leq k \leq 10000\)
3	21	\(1 \leq n \leq 2000\)
4	27	The tree is a line; every vertex has degree at most 2.
5	29	No additional constraints

Input format

The first line contains one integer \(n\).

The second line contains one integer \(k\).

The third line contains \(n - 1\) integers, the \(i^{th}\) of which represents the first endpoint of the \(i^{th}\) edge (vertices 0-indexed).

The fourth line contains \(n - 1\) integers, the \(i^{th}\) of which represents the second endpoint of the \(i^{th}\) edge.

The fifth line contains one integer \(|I|\), the size of \(I\).

The sixth line contains \(I\) integers \(I_1, I_2, \ldots, I_{|I|}\), representing the elements of \(I\). It is guaranteed that \(I\) is a valid independent set.

Output format

Let your answer be the independent set \(S\) (If there is no valid \(S\), let \(S = \emptyset\)). Output one line containing \(|S|\) integers, the elements of \(S\) in ascending order.

Samples

Sample Input 1	Sample Output 1
10 4 0 1 1 1 1 4 0 7 0 1 2 3 4 5 6 7 8 9 3 5 8 9	6 7 9