영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
N friends live on each vertex in a tree with N vertices, where N is an odd number. A tree is a connected graph with exactly N-1 edges.
The friends want to meet at one vertex in the tree. They have agreed that the best meeting place is the vertex that minimizes the sum of distances to the friends, and have asked you to help them find this optimal meeting place. The distance dist(a,b) between two vertices a and b in the tree is the number of edges on the path between a and b. So formally, the goal is to find the vertex x that minimizes ∑_{i=1}^n dist(x,i).
You think this is an easy problem, and start writing a solution right away. But there is a twist! The friends have bad memory and don't remember what the tree looks like. However, they do remember the following: given three different friends a,b,c, they can tell you the vertex where those three usually meet, which is the vertex x that minimizes dist(x,a) +dist(x,b) +dist(x,c). Note that x is not necessarily one of the vertices a, b or c.
In this problem you will not read the graph from the input, instead you can ask Q-1 questions on the form: Where do the friends a,b,c usually meet? Your task is to find the optimal meeting place by using these questions.
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: The tree in the sample. Vertex 2 is the optimal meeting place.
Interaction
The first line of input contains two integers N and Q, the number of vertices in the tree, and the number of queries you can make. It is guaranteed that N is odd and that Q = 500000 in all test cases.
Then you can make the following queries:
- Output one line with “
? a b c” where 1 ≤ a,b,c ≤ N are 3 different friends. After that, the judge will respond with one integer x that you should read from input (1 ≤ x ≤ N), the vertex that minimizes dist(x,a) +dist(x,b) +dist(x,c). - Output one line with “
! x” where 1 ≤ x ≤ N is the optimal meeting place. After you have printed this query your program should terminate without outputting anything more. If x is the vertex that minimizes ∑_{i=1}^n dist(x,i) you will get Accepted on the test case, otherwise you will get Wrong Answer.
If you make more than Q queries (including the last on the form “! x”) your program will be terminated and you will get Wrong Answer.
Make sure to flush the output after each query, otherwise you may get Time Limit Exceeded. In C++ this can be done for example with cout << flush or fflush(stdout); in Python with stdout.flush(); and in Java with System.out.flush().
Scoring
Your solution will be tested on a set of test case groups. To get points for a group, you must pass all test cases in the group.
| Group | Points | Constraints |
| 1 | 10 | 3 ≤ N ≤ 99 and all vertices have degree at most 2 (the tree is a line) |
| 2 | 12 | 3 ≤ N ≤ 999 and all vertices have degree at most 2 (the tree is a line) |
| 3 | 21 | 3 ≤ N ≤ 24999 and all vertices have degree at most 2 (the tree is a line) |
| 4 | 14 | 3 ≤ N ≤ 99 |
| 5 | 15 | 3 ≤ N ≤ 999 |
| 6 | 28 | 3 ≤ N ≤ 24999 |