Codeforces Round 906 (Div. 1)
A. Qingshan Loves Strings 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Qingshan has a string $$$s$$$ which only contains $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

A string $$$a$$$ of length $$$k$$$ is good if and only if

  • $$$a_i \ne a_{k-i+1}$$$ for all $$$i=1,2,\ldots,k$$$.

For Div. 2 contestants, note that this condition is different from the condition in problem B.

For example, $$$\texttt{10}$$$, $$$\texttt{1010}$$$, $$$\texttt{111000}$$$ are good, while $$$\texttt{11}$$$, $$$\texttt{101}$$$, $$$\texttt{001}$$$, $$$\texttt{001100}$$$ are not good.

Qingshan wants to make $$$s$$$ good. To do this, she can do the following operation at most $$$300$$$ times (possibly, zero):

  • insert $$$\texttt{01}$$$ to any position of $$$s$$$ (getting a new $$$s$$$).

Please tell Qingshan if it is possible to make $$$s$$$ good. If it is possible, print a sequence of operations that makes $$$s$$$ good.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n\le 100$$$) — the length of string $$$s$$$, respectively.

The second line of each test case contains a string $$$s$$$ with length $$$n$$$.

It is guaranteed that $$$s$$$ only consists of $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

Output

For each test case, if it impossible to make $$$s$$$ good, output $$$-1$$$.

Otherwise, output $$$p$$$ ($$$0 \le p \le 300$$$) — the number of operations, in the first line.

Then, output $$$p$$$ integers in the second line. The $$$i$$$-th integer should be an index $$$x_i$$$ ($$$0 \le x_i \le n+2i-2$$$) — the position where you want to insert $$$\texttt{01}$$$ in the current $$$s$$$. If $$$x_i=0$$$, you insert $$$\texttt{01}$$$ at the beginning of $$$s$$$. Otherwise, you insert $$$\texttt{01}$$$ immediately after the $$$x_i$$$-th character of $$$s$$$.

We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most $$$300$$$ operations.

Example
Input
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
Output
0

-1
-1
2
6 7
1
10
-1
Note

In the first test case, you can do zero operations and get $$$s=\texttt{01}$$$, which is good.

Another valid solution is to do one operation: (the inserted $$$\texttt{01}$$$ is underlined)

  1. $$$\texttt{0}\underline{\texttt{01}}\texttt{1}$$$

and get $$$s = \texttt{0011}$$$, which is good.

In the second and the third test case, it is impossible to make $$$s$$$ good.

In the fourth test case, you can do two operations:

  1. $$$\texttt{001110}\underline{\texttt{01}}$$$
  2. $$$\texttt{0011100}\underline{\texttt{01}}\texttt{1}$$$

and get $$$s = \texttt{0011100011}$$$, which is good.

B. Doremy's Connecting Plan
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Doremy lives in a country consisting of $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$, with $$$a_i$$$ people living in the $$$i$$$-th city. It can be modeled as an undirected graph with $$$n$$$ nodes.

Initially, there are no edges in the graph. Now Doremy wants to make the graph connected.

To do this, she can add an edge between $$$i$$$ and $$$j$$$ if

$$$$$$ \sum_{k \in S} a_k \ge i\cdot j \cdot c, $$$$$$

where $$$S$$$ is the set of all the nodes that are currently in the same connected component of either $$$i$$$ or $$$j$$$, and $$$c$$$ is a given constant.

Can Doremy make the graph connected?

Two nodes $$$(i, j)$$$ are in the same connected component if there exists a path from $$$i$$$ to $$$j$$$. A graph is connected if all its nodes are in the same connected component.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains two integers $$$n$$$, $$$c$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$1 \le c \le 10^6$$$) — the number of nodes and the constant.

The second line of each test case contains $$$ n $$$ integers $$$ a_1,a_2,\ldots,a_n $$$ ($$$0 \le a_i \le 10^{12}$$$) — the number of people living in the $$$i$$$-th city.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print "YES" (without quotes), if it is possible to make the graph connected, and "NO" (without quotes) otherwise.

You can print letters in any case (upper or lower).

Example
Input
7
4 10
0 20 15 10
2 1
1 1
5 1
0 1 0 4 199
5 2
1 1 3 1 1
5 5
5 6 1 10 2
5 1000000
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
3 1
0 0 2
Output
Yes
Yes
Yes
No
No
Yes
No
Note

In the first test case, Doremy can add edges in the following order:

  1. Add $$$(1,2)$$$. This operation is valid because $$$a_1 + a_2 = 20 \ge i\cdot j \cdot c = 20$$$.
  2. Add $$$(1,3)$$$. This operation is valid because $$$a_1 + a_2 + a_3 = 35 \ge i \cdot j \cdot c = 30$$$.
  3. Add $$$(1,4)$$$. This operation is valid because $$$a_1 + a_2 + a_3 + a_4 = 45 \ge i \cdot j \cdot c = 40$$$.

In the second test case, Doremy can add edge $$$(1,2)$$$ because $$$a_1 + a_2 =2 \ge 1 \cdot 2 \cdot 1$$$. After that, the graph is connected.

In the third test case, Doremy can add edges in the order $$$(5,4)$$$, $$$(5,3)$$$, $$$(5,2)$$$ and $$$(5,1)$$$.

In the fourth test case, Doremy cannot add any edge at all.

C1. Doremy's Drying Plan (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only differences between the two versions of this problem are the constraint on $$$k$$$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.

Doremy lives in a rainy country consisting of $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$.

The weather broadcast predicted the distribution of rain in the next $$$m$$$ days. In the $$$i$$$-th day, it will rain in the cities in the interval $$$[l_i, r_i]$$$. A city is called dry if it will never rain in that city in the next $$$m$$$ days.

It turns out that Doremy has a special power. She can choose $$$k$$$ days (in the easy version, $$$k = 2$$$), and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$k = 2$$$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.

Then, $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the rain coverage on day $$$i$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output one integer — the maximum number of dry cities.

Example
Input
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 2
1 5
6 10
2 2
3 7
5 8
1 4
100 6 2
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 2
9 20
3 3
10 11
11 13
6 18
Output
1
2
3
0
1000
15
Note

In the first test case, if Doremy prevents

  • rain $$$1,2$$$, then city $$$2$$$ will be dry;
  • rain $$$2,3$$$, then no city will be dry;
  • rain $$$1,3$$$, then no city will be dry;

So there is at most $$$1$$$ dry city.

In the second test case, if Doremy prevents

  • rain $$$1,2$$$, then city $$$1,2$$$ will be dry;
  • rain $$$2,3$$$, then city $$$4,5$$$ will be dry;
  • rain $$$1,3$$$, then city $$$1,5$$$ will be dry.

So there are at most $$$2$$$ dry cities.

In the third test case, it is optimal to prevent rain $$$2,5$$$.

In the forth test case, there is always $$$4$$$ days of rain that wets all the cities and cannot be prevented.

C2. Doremy's Drying Plan (Hard Version)
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The only differences between the two versions of this problem are the constraint on $$$k$$$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.

Doremy lives in a rainy country consisting of $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$.

The weather broadcast predicted the distribution of rain in the next $$$m$$$ days. In the $$$i$$$-th day, it will rain in the cities in the interval $$$[l_i, r_i]$$$. A city is called dry if it will never rain in that city in the next $$$m$$$ days.

It turns out that Doremy has a special power. She can choose $$$k$$$ days, and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$2 \le k \le \min(10, m)$$$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.

Then, $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the rain coverage on day $$$i$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output one integer — the maximum number of dry cities.

Example
Input
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 4
1 5
6 10
2 2
3 7
5 8
1 4
100 6 5
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 3
9 20
3 3
10 11
11 13
6 18
Output
1
2
6
0
1000
17
Note

In the first test case, if Doremy prevents

  • rain $$$1,2$$$, then city $$$2$$$ will be dry;
  • rain $$$2,3$$$, then no city will be dry;
  • rain $$$1,3$$$, then no city will be dry;

So there is at most $$$1$$$ dry city.

In the second test case, if Doremy prevents

  • rain $$$1,2$$$, then city $$$1,2$$$ will be dry;
  • rain $$$2,3$$$, then city $$$4,5$$$ will be dry;
  • rain $$$1,3$$$, then city $$$1,5$$$ will be dry.

So there are at most $$$2$$$ dry cities.

In the third test case, it is optimal to prevent rain $$$1,2,4,5$$$.

In the forth test case, there is always a day of rain that wets all the cities and cannot be prevented.

D. Game of Stacks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ stacks $$$r_1,r_2,\ldots,r_n$$$. Each stack contains some positive integers ranging from $$$1$$$ to $$$n$$$.

Define the following functions:

function init(pos):
    stacks := an array that contains n stacks r[1], r[2], ..., r[n]
    return get(stacks, pos)

function get(stacks, pos):
    if stacks[pos] is empty:
        return pos
    else:
        new_pos := the top element of stacks[pos]
        pop the top element of stacks[pos]
        return get(stacks, new_pos)

You want to know the values returned by $$$\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}$$$.

Note that, during these calls, the stacks $$$r_1,r_2,\ldots,r_n$$$ don't change, so the calls $$$\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}$$$ are independent.

Input

The first line of the input contains one integer $$$n$$$ ($$$1\le n\le 10^5$$$) — the length of the array $$$r$$$.

Each of the following $$$n$$$ lines contains several integers. The first integer $$$k_i$$$ ($$$0\le k_i\le 10^5$$$) represents the number of elements in the $$$i$$$-th stack, and the following $$$k_i$$$ positive integers $$$c_{i,1},c_{i,2},\ldots,c_{i,k_i}$$$ ($$$1\le c_{i,j}\le n$$$) represent the elements in the $$$i$$$-th stack. $$$c_{i,1}$$$ is the bottom element.

In each test, $$$\sum k_i\le 10^6$$$.

Output

You need to output $$$n$$$ values, the $$$i$$$-th of which is the value returned by $$$\texttt{init(i)}$$$.

Examples
Input
3
3 1 2 2
3 3 1 2
3 1 2 1
Output
1 2 2
Input
5
5 1 2 4 3 4
6 1 2 5 3 3 4
6 1 1 4 4 4 2
9 3 1 4 2 3 5 5 1 2
4 4 4 1 3
Output
1 1 1 1 1
Note

In the first example:

  • When you call $$$\texttt{init(1)}$$$, set $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1,2],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 3}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is empty, return $$$1$$$.
  • When you call $$$\texttt{init(2)}$$$, set $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2,2],[3,1],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2,2],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 3}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is empty, return $$$2$$$.
  • When you call $$$\texttt{init(3)}$$$, set $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, and then call $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2,2],[3,1,2],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1,2],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[3],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 3}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ is empty, return $$$2$$$.

E. Doremy's Swapping Trees
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Consider two undirected graphs $$$G_1$$$ and $$$G_2$$$. Every node in $$$G_1$$$ and in $$$G_2$$$ has a label. Doremy calls $$$G_1$$$ and $$$G_2$$$ similar if and only if:

  • The labels in $$$G_1$$$ are distinct, and the labels in $$$G_2$$$ are distinct.
  • The set $$$S$$$ of labels in $$$G_1$$$ coincides with the set of labels in $$$G_2$$$.
  • For every pair of two distinct labels $$$u$$$ and $$$v$$$ in $$$S$$$, the corresponding nodes are in the same connected component in $$$G_1$$$ if and only if they are in the same connected component in $$$G_2$$$.

Now Doremy gives you two trees $$$T_1$$$ and $$$T_2$$$ with $$$n$$$ nodes, labeled from $$$1$$$ to $$$n$$$. You can do the following operation any number of times:

  • Choose an edge set $$$E_1$$$ from $$$T_1$$$ and an edge set $$$E_2$$$ from $$$T_2$$$, such that $$$\overline{E_1}$$$ and $$$\overline{E_2}$$$ are similar. Here $$$\overline{E}$$$ represents the graph which is given by only reserving the edge set $$$E$$$ from $$$T$$$ (i.e., the edge-induced subgraph). In other words, $$$\overline{E}$$$ is obtained from $$$T$$$ by removing all edges not included in $$$E$$$ and further removing all isolated vertices.
  • Swap the edge set $$$E_1$$$ in $$$T_1$$$ with the edge set $$$E_2$$$ in $$$T_2$$$.

Now Doremy is wondering how many distinct $$$T_1$$$ you can get after any number of operations. Can you help her find the answer? Output the answer modulo $$$10^9+7$$$.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 2\cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the number of nodes in the trees $$$T_1$$$ and $$$T_2$$$.

Each of the following $$$n-1$$$ lines contain two integers $$$u,v$$$ ($$$1\le u,v\le n$$$), representing an undirected edge in $$$T_1$$$. It is guaranteed these edges form a tree.

Each of the following $$$n-1$$$ lines contain two integers $$$u,v$$$ ($$$1\le u,v\le n$$$), representing an undirected edge in $$$T_2$$$. It is guaranteed these edges form a tree.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, you should output a single line with an integer, representing the number of distinct $$$T_1$$$ after any number of operations, modulo $$$10^9+7$$$.

Example
Input
3
2
1 2
2 1
3
1 3
2 3
2 3
2 1
4
1 2
2 3
3 4
4 2
2 1
1 3
Output
1
2
4
Note

In the first test case, there is at most one distinct $$$T_1$$$ having the only edge $$$(1,2)$$$.

In the second test case, you can choose the edge set $$$\{(1,3),(2,3)\}$$$ in $$$T_1$$$, the edge set $$$\{(1,2),(2,3)\}$$$ in $$$T_2$$$ and swap them. So $$$T_1$$$ can be $$$1-3-2$$$ or $$$1-2-3$$$.

In the third test case, there are $$$4$$$ distinct $$$T_1$$$, as the following pictures.

F. Doremy's Average Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Doremy has a rooted tree of size $$$n$$$ whose root is vertex $$$r$$$. Initially there is a number $$$w_i$$$ written on vertex $$$i$$$. Doremy can use her power to perform this operation at most $$$k$$$ times:

  1. Choose a vertex $$$x$$$ ($$$1 \leq x \leq n$$$).
  2. Let $$$s = \frac{1}{|T|}\sum_{i \in T} w_i$$$ where $$$T$$$ is the set of all vertices in $$$x$$$'s subtree.
  3. For all $$$i \in T$$$, assign $$$w_i := s$$$.

Doremy wants to know what is the lexicographically smallest$$$^\dagger$$$ array $$$w$$$ after performing all the operations. Can you help her?

If there are multiple answers, you may output any one.

$$$^\dagger$$$ For arrays $$$a$$$ and $$$b$$$ both of length $$$n$$$, $$$a$$$ is lexicographically smaller than $$$b$$$ if and only if there exist an index $$$i$$$ ($$$1 \leq i \le n$$$) such that $$$a_i \lt b_i$$$ and for all indices $$$j$$$ such that $$$j \lt i$$$, $$$a_j=b_j$$$ is satisfied.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $$$n$$$, $$$r$$$, $$$k$$$ ($$$2 \le n \le 5000$$$, $$$1 \le r \le n$$$, $$$0 \le k \le \min(500,n)$$$).

The second line contains $$$n$$$ integers $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le 10^6$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), representing an edge between $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$50\,000$$$.

Output

For each test case, In the first line, output a single integer $$$cnt$$$ ($$$0 \le cnt \le k$$$) — the number of operations you perform.

Then, in the second line output $$$cnt$$$ integers $$$p_1,p_2,\ldots,p_{cnt}$$$ — $$$x$$$ is chosen to be $$$p_i$$$ for $$$i$$$-th operation.

If there are multiple answers, you may output any one.

Example
Input
4
6 1 1
1 9 2 6 1 8
1 2
1 3
2 4
3 6
3 5
7 7 2
3 1 3 3 1 1 2
7 1
7 2
7 4
1 5
2 3
4 6
6 5 1
3 1 3 1 1 3
5 3
5 1
5 6
3 4
1 2
3 2 1
1000000 999999 999997
2 1
1 3
Output
1
2
2
1 4
1
5
1
1
Note

In the first test case:

At first $$$w=[1,9,2,6,1,8]$$$. You can choose some vertex $$$x$$$ to perform at most one operation.

  • If $$$x=1$$$, $$$w=[\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2}]$$$.
  • If $$$x=2$$$, $$$w=[1,\frac{15}{2},2,\frac{15}{2},1,8]$$$.
  • If $$$x=3$$$, $$$w=[1,9,\frac{11}{3},6,\frac{11}{3},\frac{11}{3}]$$$.
  • If $$$x \in \{4, 5, 6\}$$$, $$$w=[1,9,2,6,1,8]$$$.
  • If you don't perform any operation, $$$w=[1,9,2,6,1,8]$$$.

$$$w$$$ is lexicographically smallest when $$$x=2$$$.