题目内容

在一座古老的城堡中，有 $n$ 间密室，它们由若干条双向通道连接，形成了一棵以密室 $1$ 为根的有根树形结构。每间密室至多拥有两个直接相连的下层密室。为了方便探索，人们给每间密室标定了一组二维坐标 $(x_i, y_i)$：根密室 $1$ 的坐标为 $(0,0)$。对于一间父密室坐标为 $(x,y)$，将其下层的密室按编号从小到大排序：编号较小的密室作为左分支密室（若仅有一间下层密室也视为左分支），其坐标为 $(x-1, y-1)$；若存在第二间下层密室，则作为右分支密室，其坐标为 $(x+1, y-1)$。

定义两间密室 $u$ 和 $v$ 的「网格距离」为 $|x_u - x_v| + |y_u - y_v|$。现在有 $q$ 次询问，每次给出两间密室的编号，请你计算它们之间的网格距离。

密室个数 $n$ 和询问次数 $q$ 均不超过 10^5。输入保证给出的结构是一棵有根树，根为 $1$，每个节点至多有两个子节点，且编号较小的子节点为左子节点（若仅有一个子节点则视为左子节点）。

输入描述

第一行包含两个整数 $n$ 和 $q$，表示密室个数和询问次数。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示密室 $u$ 与密室 $v$ 之间有一条双向通道。