Nils has a hidden tree, which he uses to challenge Josh and Mike! The tree has
First, Nils will show Josh the tree. Then, Josh will create a sequence of
Next, Mike will be asked
In the
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
Can you help Josh and Mike devise an optimal strategy?
Constraints
The edges form a tree.
Scoring
If any query is answered incorrectly, the program will score
Otherwise, let
Score | |
---|---|
The score for the problem is equal to the minimum score on any test case.
Grading Environment
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
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
If the integer on the first line is
If the integer on the first line is -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.
Comments