Interactive Vertex

시간 제한2초메모리 제한512 MB

요약

트리에서 숨겨진 특별 정점을 찾아야 한다. 각 질의는 정점 x와 정점 집합을 주면 x가 집합의 모든 정점보다 특별 정점에 가깝거나 같은지 알려준다. 질의 횟수는 4*ceil(log2 n) 이하로 제한된다.

난이도: 어려움10점 중 9점
유형: 트리, 분할 정복, 이분 탐색, 구간
정답자: 아직 제출이 없습니다

문제

This is an interactive problem.

Endagorion has a tree on $n$ vertices, and he also showed it to you. He chooses one vertex $u$ as a special vertex, but now he won't tell you anything about it!

Instead, you can ask him questions. For each question, you should choose a vertex $x$ , an integer $k$ , and $k$ vertices $v\_1, v\_2, \ldots, v\_k$ , and he will tell you whether it is true that $\min{(\mathrm{dist}(u, v\_i))} \geq \mathrm{dist}(u, x)$ . Here, $\mathrm{dist}(p, q)$ is the number of edges in the simple path between vertices $p$ and $q$ in the tree.

You should guess the special vertex using at most $4{\lceil}\log\_2{n}{\rceil}$ queries.

Endagorion is very honest, so he wouldn't change the vertex between your queries (in other words, the interactor is not adaptive).

As the constraints are large, and flush is an expensive operation, make sure that you are not flushing too often. You may do it only once after each query.

힌트

예제3

예제 1
입력
```
5
1 2
1 3
1 4
1 5
1
```
예상 출력
```
? 4 1 2 3 4 5
! 1
```

예제 2

입력

예상 출력

? 4 1 2 3 4 5
? 3 1 2 3 4
? 2 1 2 3
? 1 1 2
! 2

예제 3

입력

예상 출력

? 3 3 5 7 1
! 3