## Yet Another Contest 8 P5 - Hidden Tree

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

Nils has a hidden tree, which he uses to challenge Josh and Mike! The tree has nodes and bidirectional edges, with the -th edge connecting nodes and .

First, Nils will show Josh the tree. Then, Josh will create a sequence of integers , satisfying .

Next, Mike will be asked queries about the tree. Note that Mike does not know Nils' tree or Josh's sequence, or even the value of .

In the -th query, Nils will select two non-adjacent nodes and . Mike will be told the values of and , and is challenged to respond with any integer such that node lies on the unique simple path between nodes and on the tree, with and .

Josh and Mike are working as a team, so they should decide on a shared strategy such that Josh's choice of sequence allows Mike to correctly answer his queries. When Josh is able to choose large integers, more information can be passed to Mike. Thus, Josh is challenged to minimize the maximum value in , whilst still communicating enough information for Mike to answer all queries correctly.

Can you help Josh and Mike devise an optimal strategy?

#### Constraints

. No edge will exist between nodes and .

The edges form a tree.

#### Scoring

If any query is answered incorrectly, the program will score points.

Otherwise, let be the maximum value in the sequence made by your program in any test case. Let . Your program will receive the following score:

Score

The score for the problem is equal to the minimum score on any test case.

Your program will be executed in two separate processes. The first process will play the role of Josh, whilst the second process will play the role of Mike. This is to ensure that no global variables are shared between the processes.

Note that the queries for the second process are based off the output of the first process. Additionally, the correctness of the second process will be judged based on the tree given as an input to the first process.

Additionally, an interactive judge is used. This means that each query must be answered before the next one is given. The interactor is not adaptive in the sense that the pairs of nodes and are predetermined.

Finally, the sum of the execution times across the two processes will be compared against the time limit. The time taken by the interactor does not count towards the time limit. The memory used by each of the processes will separately be compared against the memory limit.

#### Interaction

The first line contains a single integer, either or .

If the integer on the first line is , then your program should play the role of Josh. The second line will contain a single integer, . The -th of the following lines will contain two space-separated integers, and . You should then output a single line of space-separated integers, .

If the integer on the first line is , then your program should play the role of Mike. The second line will contain a single integer, . Then, you should answer queries. For the -th query, you should read in a line containing two space-separated integers, and . You should then output the answer to the -th query on a separate line. If at any point your answer is formatted incorrectly or is incorrect, the interactor will respond with -1 -1 on a single line. After receiving this feedback, you should terminate your program to receive a Wrong Answer verdict; otherwise, your program will receive an arbitrary verdict.

Please note that you may need to flush stdout after outputting your chosen array and after answering each query, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

#### Sample Interaction 1

1
5
1 2
2 3
2 4
4 5
>>> 10 13 11 15 12

#### Sample Interaction 2

2
3
10 11
>>> 2
10 12
>>> 4
11 12
>>> 4

In the sample interactions above, >>> denotes your output. Do not print this out.