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,\dots ,a_{|A|}$ in ascending order; and similarly, let the indices in $B$ be $b_1,b_2,\dots ,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\le n\le {10}^6$
$1\le k\le {10}^{18}$

Subtasks #	Score	Constraints
1	6	$1\le n\le 20$
2	17	$1\le n\le 2000$ $1\le k\le 10000$
3	21	$1\le n\le 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,\dots ,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=\mathrm{\varnothing }$). 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