DMOPC '19 Contest 2 P6 - Two Roots

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 128M

Author:
Problem types

You are given a tree consisting of nodes. Bob has chosen two distinct nodes, and , which you are to determine. You can ask up to queries of the form: and Bob will tell you the distance between the lowest common ancestor of if the tree were rooted at and the lowest common ancestor of if the tree were rooted at . The lowest common ancestor of is defined as the node furthest from the root such that it contains each of in its subtree. The distance between two nodes and is defined as the number of edges on the unique shortest path from to .

If your program exceeds the query limit or makes an invalid query, the interactor will print -1. Make sure your program terminates immediately after reading -1 or you may get an arbitrary verdict.

Note: the interactor will take up approximately 1 second of execution time.

Constraints

The degree of each node is at most .

Input Specification

The first line of input contains one integer, .
The next lines of input contain two space-separated integers, , indicating that there is an edge between to .
The next -th line contains one integer which is Bob's answer to your -th query.

Output Specification

For a query, print ? k x_1 x_2 ... x_k on a new line where is the number of nodes you want to query and are the nodes.
When you have the answer, print ! A B where and are the nodes Bob chose in any order.

Sample Interaction

>>> denotes your program's output. Don't actually print this out.

8
1 2
1 3
1 8
2 7
3 4
3 5
3 6
>>> ? 2 2 5
3
>>> ? 3 4 1 6
1
>>> ? 2 8 4
1
>>> ! 2 5