Dirty Politics

Limits 3s, 256 MB · Interactive

This is an interactive problem. (If you want to know about interactive problems, click here)

Your country is on a war. The map of your enemy country can be represented with $n$ states connected by $n-1$ bidirectional roads in such a way that you can go from any state to any other state within the country using these roads. Each state has a governor who is affiliated to either of the two political parties - Onliners and Offliners. Due to extremely high security it is impossible for you to know which governor is of which party. Fortunately, there are severe political rivalries among your enemies. For example, if two states connected by a road have two governors from different parties, the road is kept blocked; otherwise the road is kept unblocked. So your commander-in -general decided to give you the following task.

You can choose some governor to bribe. Then the governor will do the following things in the given order:

1. The governor will tell you how many of his neighbor states (those having a shared road with his state) have a governor of his party.

2. Consequently, the governor will be banished from his party. Then he will join the opposition party. As a result, block-unblock states of the roads will change accordingly.

You can bribe at most $\lfloor \frac{3n - 2}{2} \rfloor$ times due to budget limitations. You can bribe a particular governor multiple times. You have to bribe the governors in such a way that all of the $n-1$ roads of your enemy country becomes blocked when your job is complete. Now it is time to go for your country!

Input

The first line contains an integer $T$ ( $1 \le T \le 40$ ), the number of test cases.

Each of the test cases begins with an integer $n$ ( $2\le n\le 10^5$ ), the number of states your enemy-country has.

Each of the next $n-1$ lines will contain two integers $u$ and $v$, ($1\le u \lt v \le n$) indicating there is a road between state $u$ and state $v$.

$\sum n$ over all test cases will not exceed $3*10^5$ in a single file.

Output

You can interact in two ways:

• To bribe the governor of state $x$ ( $1\le x \le n$ ), print

  x
  

  You will be responded with

  y
  

  where $y$ ( $0 \le y \lt n$ ) is the number of neighbor states of state $x$ having a governor of the political party that the governor of $x$ currently affiliated to. After answering to your query, the governor of state $x$ will change his party.

• To declare that your job is done, print

  0
  

  If your job for this enemy-country (i.e. test case) is done successfully, the response is

  0
  

You will be responded with -1 if you make a wrong query or a query beyond limitation i.e. trying to bribe despite you ran out of budget (declaring the job is done is not counted as bribing) or there are some roads still remaining unblocked but you have declared your job done. Then you should terminate your program immediately in order to avoid deceptive verdicts like CPU Limit Exceeded, Memory Limit Exceeded etc. Finally, don’t forget to flush your output after printing each line.

Here is an example. First You take input $T$, the number of test cases.

2

Now you will take input for the first case.

2
1 2

Then a possible interaction can be as following:

< 1
> 0
< 1
> 1
< 0
> 0

Query Simulation: Red edges indicate blocked state; blue ones are for unblocked roads.

Similarly, for the second test:

4
1 3
2 3
3 4

A possible interaction:

< 3
> 1
< 1
> 1
< 2
> 0
< 2
> 1
< 4
> 1
< 0
> 0

Here, the following things happen

> indicates what your program reads and < indicates what your program writes. These symbols are here to make it easy to understand. You do not have to read > and don’t print < in your program.