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
For all subtasks:
Subtask 1 [30%]
Subtask 2 [20%]
The degree of each node is at most .
Subtask 3 [50%]
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
Comments