思路与结论

关键观察

• 由定义可知：每向下一层，$y$ 坐标减 $1$，因此对任意结点 $i$，有 $y_i = -\text{depth}(i),$ 其中 $\text{depth}(1)=0$。
• $x$ 坐标从根开始：走到左儿子 $x$ 减 $1$，走到右儿子 $x$ 加 $1$。 因而 $x_i$ 等于从根到 $i$ 的路径上“右转次数减去左转次数”。

题目内容

小红有一棵$n$个结点的二叉树，根结点为1。

定义树上一个点的坐标为$(xi,yi)$，根结点的坐标为$(0,0)$。

一个结点若有两个子结点，那么我们称编号较小的结点为左儿子，编号较大的为右儿子，若只有一个结点，默认其为左儿子。

若一个结点的父结点坐标为$(a,b)$，如果该结点为父结点的左儿子，那么此结点的坐标为$(a-1,b-1)$，如果该结点为父结点的右儿子，那么该结点的坐标为$(a+1,b-1)$。

定义两点的树上曼哈顿距离为$|x_1- x_2|+|y_1- y_2|$。

现在小红会提出若干个询问，每次给出两个点，请你回答两点的树上曼哈顿距离。

输入描述

第一行两个整数$n,q(1≤n,q≤10^5)$，表示结点个数和询问次数。

接下来$n-1$行，每行$2$个整数$u,v(1≤u,≤n,u≠v)$,表示$u,v$之间存在一条无向边。

接下来$q$行，每行两个整数$x,y(1≤x,y≤n)$，表示询问的点对。

输入保证是一棵二叉有根树。

输出描述

$q$ 行，每行一个整数，两个点的树上曼哈顿距离。

样例1

输入

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

输出

6
4

说明

五个点的坐标分别为 $(0, 0), (-1,-1),(-2,-2),(0,-2),(-3,-3)$。