만남의 장소

$N$명의 친구가 각자 $N$개의 노드로 이루어진 트리의 노드 한 개씩에 살고 있다. $N$은 홀수이다. 트리는 간선이 정확히 $N-1$개인 연결 그래프이다.

친구들은 트리의 한 노드에서 모이려고 한다. 모든 친구까지 거리의 합이 가장 작은 노드를 만남의 장소로 정하기로 했고, 이 최적의 장소를 찾아 달라고 부탁했다. 두 노드 $a$와 $b$ 사이의 거리 $\text{dist}(a,b)$는 두 노드를 잇는 경로의 간선 수이다. 정식으로 말하면, $\sum_{i=1}^{n} \text{dist}(x,i)$를 최소로 하는 노드 $x$를 찾아야 한다.

친구들은 트리의 모양을 기억하지 못한다. 대신 서로 다른 세 친구 $a$, $b$, $c$가 주어지면, (그 셋만 있을 때) $\text{dist}(x,a)+\text{dist}(x,b)+\text{dist}(x,c)$를 최소로 하는 노드 $x$에서 모인다는 것은 기억하고 있다. $x$가 반드시 $a$, $b$, $c$ 중 하나일 필요는 없다.

트리는 입력으로 주어지지 않는다. 세 친구 $a$, $b$, $c$가 주로 어디에서 모이는지 묻는 질문을 최대 $Q-1$번까지 할 수 있다. 이 질문들로 최적의 만남의 장소를 찾아야 한다.

예시 트리의 그림이다. 노드 2가 최적의 만남의 장소이다.

$3 \le N\le 24\,999$