You are given a tree consisting of ~N~ nodes. Bob has chosen two distinct nodes, ~A~ and ~B~, which you are to determine. You can ask up to ~Q~ queries of the form: ~k\ x_1\ x_2 \dots x_k~ and Bob will tell you the distance between the lowest common ancestor of ~x_1, x_2, \dots, x_k~ if the tree were rooted at ~A~ and the lowest common ancestor of ~x_1, x_2, \dots, x_k~ if the tree were rooted at ~B~. The lowest common ancestor of ~x_1, x_2, \dots, x_k~ is defined as the node furthest from the root such that it contains each of ~x_1, x_2, \dots, x_k~ in its subtree. The distance between two nodes ~a~ and ~b~ is defined as the number of edges on the unique shortest path from ~a~ to ~b~.
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.
For all subtasks:
~2 \le N \le 1000~
Subtask 1 [30%]
~Q = 1000~
Subtask 2 [20%]
The degree of each node is at most ~2~.
~Q = 128~
Subtask 3 [50%]
~Q = 40~
The first line of input contains one integer, ~N~.
The next ~N-1~ lines of input contain two space-separated integers, ~x_i~ ~y_i~, indicating that there is an edge between ~x_i~ to ~y_i~.
The next ~i~-th line contains one integer which is Bob's answer to your ~i~-th query.
For a query, print
? k x_1 x_2 ... x_k on a new line where ~k~ is the number of nodes you want to query and ~x_1, x_2, \dots, x_k~ are the nodes.
When you have the answer, print
! A B where ~A~ and ~B~ are the nodes Bob chose in any order.
>>> 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