CF1761G.Centroid Guess

This in an interactive problem.

There is an unknown tree consisting of $n$ nodes, which has exactly one centroid. You only know $n$ at first, and your task is to find the centroid of the tree.

You can ask the distance between any two vertices for at most $2\cdot10^5$ times.

Note that the interactor is not adaptive. That is, the tree is fixed in each test beforehand and does not depend on your queries.

A vertex is called a centroid if its removal splits the tree into subtrees with at most $\lfloor\frac{n}{2}\rfloor$ vertices each.

这是一个交互式问题。

存在一棵未知的、包含 $n$ 个节点的树，该树恰好有一个重心。你最初仅知道 $n$，任务是找出这棵树的重心。

你最多可询问任意两个顶点之间的距离 $2\cdot10^5$ 次。

注意：评测程序是非自适应的。也就是说，每组测试用例中的树在开始时即已固定，不依赖于你的查询。

若一个顶点被移除后，所生成的所有子树的大小均不超过 $\lfloor\frac{n}{2}\rfloor$，则称该顶点为重心。

The only line of the input contains an integer $n$ ($3\le n\le 7.5\cdot10^4$) — the number of nodes in the tree.

输入仅包含一行，一个整数 $n$（$3\le n\le 7.5\cdot10^4$），表示树中节点的数量。

Here is an image of the tree from the sample.

以下是样例中的树的图像。