题目描述

给定一棵 $n$ 个结点的无根树，结点编号 $1\sim n$。我们把它当成以 $1$ 号结点为根的有根树。

接下来有 $q$ 次询问，每次给出两个结点 $u,v$，请求出它们的最近公共祖先（即 $u$ 到根的路径与 $v$ 到根的路径的第一个交点）。

输入格式

第一行两个整数 $n,q$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示结点 $u$ 与结点 $v$ 之间有一条边，保证这些边构成一棵树。

接下来 $q$ 行，每行两个整数 $u,v$，表示一次询问。

输出格式

共 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问的最近公共祖先编号。

输入输出样例 #1

输入 #1

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

输出 #1

2
1
2
1

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n,q\le 2\times 10^5$。