题解

题面描述

给定一棵有根的二叉树，树共有 $n$ 个结点，根结点编号为 $1$。每个结点的坐标通过其父结点的坐标确定。根结点的坐标为 $(0,0)$，每个结点的坐标依赖于其父结点的坐标以及该结点是父结点的左儿子还是右儿子。如果一个结点为父结点的左儿子，则其坐标为 $(a-1, b-1)$，如果该结点为父结点的右儿子，则其坐标为 $(a+1, b-1)$。一棵树上每一对结点的曼哈顿距离定义为它们的坐标差的绝对值之和，即

现在给定一个二叉树，树上有若干个查询，每次查询给定两个结点，要求输出这两个结点的树上曼哈顿距离。

题目内容

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

定义树上一个点的坐标为$(x_i,y_i)$，根结点的坐标为$(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

说明