# 树链还是简单一点好

## 输出格式

$q$ 行，每行两个整数 $p,dis$，表示最优的答案为 $p$，并且该点离 $x,y$ 两点的距离为 $dis$

8
1 2
2 3
2 4
1 5
5 6
5 7
7 8
5
1 3
2 5
7 4
8 8
1 5

2 1
1 1
1 2
8 0
-1


## 样例说明 1

1 2 3 4 5 6 7 8
1 0 1 2 1 2 3
2 0 1 2 3 4
3 0 2 3 4 5
4 0
5 0 1 2
6 0 2 3
7 0 1
8 0

1. $2$$1,3$ 的距离均为 $1$
2. $1$$2,5$ 的距离均为 $1$
3. $1$$7,4$ 的距离均为 $2$
4. $8$$8,8$ 的距离均为 $0$
5. 没有点离 $1,5$ 的距离相同。

## 数据规模与约定

$\texttt{Subtask 1(30 pts): } n,q \le 2 \times 10^3$
$\texttt{Subtask 2(10 pts):}$ 所有询问均满足 $x=y$
$\texttt{Subtask 3(10 pts):}$ 所有询问均满足 $x=1$
$\texttt{Subtask 3(50 pts):}$ 无特殊限制。