Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Dirty Politics

By shariful_islam · 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 nn states connected by n1n-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 3n22\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 n1n-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 TT ( 1T401 \le T \le 40 ), the number of test cases.

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

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

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

Output

You can interact in two ways:

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

    x
    

    You will be responded with

    y
    

    where yy ( 0y<n0 \le y \lt n ) is the number of neighbor states of state xx having a governor of the political party that the governor of xx currently affiliated to. After answering to your query, the governor of state xx 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 TT, 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.

Discussion

Statistics


0% Solution Ratio

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.