## CEOI '22 P3 - Prize

View as PDF

Points: 25 (partial)
Time limit: 20.0s
Memory limit: 1G

Problem types

"Living on the edge!" is a brand new TV game show that targets graph theory enthusiasts as its main audience. During each episode, the host presents a new problem for the contestants to solve. The contestant who solves the problem wins an all-inclusive trip to the Croatian coast, including a guided (Eulerian) tour of the famous Walls of Dubrovnik, as the grand prize.

Tomislav was fortunate enough to get accepted as a contestant in the next episode and immediately began his preparations. He spent countless nights at the library reading up on the most obscure theorems. One night, he accidentally fell asleep and began dreaming about his appearance on the show. Upon waking, he vividly remembered the presented problem and his inability to solve it. The problem went as follows.

The game show host drew two rooted trees, both consisting of nodes labelled with integers from to . The trees themselves are labelled with integers and . The host proceeded by stating that both trees are weighted, with positive weights, but the edge weights are purposefully kept secret. After that, Tomislav got the opportunity to choose any subset of node labels, as long as the size of that subset is exactly .

After Tomislav chose the said subset, he was able to ask at most questions of the form , where and are node labels. For each question, the host answered with an ordered quadruple , where represents the distance between nodes labelled and in tree , and represents the label of the lowest common ancestor of nodes labelled and in tree .

In order to win the prize, Tomislav had to answer a bunch of similar questions posed by the game show host. More specifically, he had to answer exactly questions of the form , where and are node labels belonging to Tomislav's chosen subset. For each question, Tomislav had to respond with the distance between nodes and in both trees, i.e. he had to provide the ordered tuple .

Your task is to help Tomislav with his preparations by writing a program that would solve the problem presented in his dream.

#### Interaction

This is an interactive task. Your program must communicate with a program made by the organizers which takes the role of the game show host. Of course, your program should take the role of Tomislav and ensure he wins the grand prize.

Your program should first read the parameters , , , and from the task description. These are given as four space-separated integers in the first line of the standard input.

Your program should proceed to read the description of two trees from the task statement. These descriptions are given in two lines, where the first line describes the first tree, while the second line describes the second tree.

Each tree is given as a sequence of space-separated integers , where represents the parent of node labelled in the tree, or is equal to if the tree is rooted in the node labelled .

Your program should then output different space-separated integers , representing the subset of node labels Tomislav should choose, and flush the output afterwards.

Your program may now ask up to questions by writing ? a b to the standard output. When your program has finished asking the questions, it should write a single character ! in its own line, and flush the output.

After that, your program may obtain the answers to the posed queries by repeatedly reading a line consisting of four space-separated integers , , , and from the task description.

Your program should proceed by reading all of the host's questions from the standard input. You must do so before writing any of your answers to the standard output. Each question is given in a single line by two space-separated integers and (where ) from the task description.

After your program has read all questions, it should answer each of them by outputting two space-separated integers , and in its own line. After printing all of the answers, your program should flush the output one last time.

#### Constraints

It is guaranteed that the hidden edge weights are positive integers not greater than .

, , trees are identical (including hidden edge weights)
,
, ,
, ,
,

#### Sample Interaction

>>> denotes your output. Do not print this out.

9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
>>> 1 5 7
>>> ? 1 5
>>> ? 1 7
>>> !
0 2 5 3
0 3 5 0
1 7
7 5
5 1
>>> 3 5
>>> 5 3
>>> 2 8

#### Explanation for Sample

In this example, the program chose the subset . Then, it asked questions and . For the first question, the lowest common ancestors of and are and , and the answer is . For the second question, the lowest common ancestors of and are and , and the answer is . Finally, the program was asked questions , , and . The answers to these questions are , , and .