溯源星树

G-14数据枢纽的外围，立着一棵由光线编织成的巨树。不是真的植物——是Zero的权限结构的可视化。每个节点是一个光球，连线是权限流。光球有白色和灰色两种状态，代表已染色和未染色。

"要进入枢纽，必须把所有节点染成白色。"Echo飘到树根处，投影和树的光融为一体，"但染色的规矩是——父节点必须先于子节点染色。一个节点只有在其父节点变白之后，才能变白。"

CC仰头看着树冠："那从根开始往下染不就行了？"

"问题是，有些节点的父节点很远。"Echo调出两个光球的连线，它们在树冠的两端，中间隔着十几层，"要判断谁是谁的祖宗，如果一层一层往上爬，太慢了。"

"预先搭梯子。"你说，"给每个节点准备好几级跳板——跳一级、跳两级、跳四级、跳八级……查询的时候，直接从最高级往下跳，像下楼梯一样。"

Echo："对。先把每个节点的深度量好，然后给它备好各级跳板。查询两个节点的最近共同祖宗时，先把深的那个往上跳到同一层，然后两个人一起从最高的跳板往下跳。"

你开始写。先给每个节点标记深度，然后预备好各级跳板——每个节点的一级、两级、四级、八级祖宗分别是谁。查询时，像两个登山者沿着梯子同时往上爬，直到碰头。

CC在旁边看着，忽然说："这棵树……好像人。"

"啥子？"

"根是祖宗，往下是分叉。一代一代，谁是谁的爹，谁是谁的儿，不就像家谱吗？"

Echo沉默了。她的投影在树的光里微微颤抖——你知道她在想什么。这棵权限树，和她记忆里的某个结构一模一样。

"染完了。"你说。屏幕上，最后一个节点从灰色变成白色。整棵树发出一阵柔和的脉动，像是一颗心脏开始跳动。

"门开了。"Echo说。

题目描述

一棵有根树，每个节点有颜色。父节点必须先于子节点染色。支持查询两个节点的最近公共祖先。用倍增预处理祖先。

输入格式

$n$。然后 $n-1$ 条边。然后 $m$ 个查询，每行两个节点编号。

输出格式

每个查询输出最近公共祖先。

输入样例

5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0

输出样例

33

提示

• 预处理每个节点的深度和第 $2^k$ 代祖先。
• 查询时先统一深度，再一起倍增上跳。
• $n, m \le 10^5$。

树形权限结构解体，露出后面真正的入口——G-14数据枢纽的安检门。门上有一排雷达感应器，扫描着任何移动的物体。

"要通过安检，必须在雷达的覆盖盲区里走。"Echo说，"每个雷达有一个圆形覆盖范围。我们要找到最少数量的点，让每个雷达的范围内至少有一个点。"

"又是覆盖？"CC皱眉。

"不，这次反过来。"你说，"上次是用板子盖住裂隙——这次是在雷达的范围内放点，让雷达以为那里是安全的。"

CC笑了："那就是骗它。"

"对。按雷达扫描范围的边缘排序，每次在最边缘放一个干扰器，能覆盖尽可能多的雷达。"