P12180 DerrickLo's City (UBC002C)

DerrickLo 看到了一个 $n \le 7.5 \times 10^5$ 的题，并且发现很多人写了 $O(n^2)$ 过了。于是他想写 $O(n\log^3n)$，但是挂了。于是将原题的序列改成了树。 注：以上故事是将出题人的名字换成 DerrickLo 得到的。

DerrickLo 在游戏中掌控着一个城市。这个城市内的团体间并不是非常的和谐，因此需要通过开会来增进关系。 已知这个组织所在的城市被分为了 $n$ 个镇，每一个镇上恰好有一个团体。其中编号为 $1$ 的镇上分布着团体 $1$，$2$ 号镇上有团体 $2$，等等。这 $n$ 个镇通过 $n-1$ 条路径相连，两两可以互相到达。 每次开会，DerrickLo 会指定一个区间 $[l, r]$，邀请编号在 $[l, r]$ 之间的团体来开会。由于团体比较分散，因此他还需要指定一个开会地址 $p$。因为团体的关系比较僵硬，所以前往开会的团体去 $p$ 的途中，不能到达别的与会团体所在的镇。 由于 DerrickLo 刚接触这个游戏，操作不太熟悉，确定 $p$ 的任务就交给你了。

无

无

对于第一个会议，$1, 2, 6$ 镇均可作为参会点。 对于第二个会议，无论选哪里作为参会点，$2, 4$ 两团体均会有一方经过另一镇。 ### 数据范围 $1 \le n, q \le 10^5$。 保证道路 $(a_i, b_i)$ 使得任意两镇可互相到达。 $1 \le l_i \le r_i \le n$。