题目描述

银河系有一个树星。

众所周知，树星的道路是树形结构，也就是说，如果树星上一共有 $n$ 座城市，那么就存在 $n-1$ 条双向道路使得各个城市间相互连通，并且默认每条道路的长度为 $1$。

小 M 是树星的一只咕噜，最近它偶然获得了一台来自人类的超空间穿梭机。

这台机器非常奇妙，只要你确定了一个目标地点，你便可以使用该机器迅速地穿梭过去。由于这台机器十分 BUG，于是树星的咕噜们便制定了限制穿梭的规则，规定小 M 必须在中转站才能使用穿梭机，而当小 M 要求使用穿梭机时，必须征得他们的同意。

具体规则如下，假定起点为 $S$，小 M 首先确定一个目标地点 $T$，然后报告树星的咕噜们，它们会为小 M 确定一个中转站 $P$,这个中转站必须位于 $S$ 和 $T$ 的正中间。若设 $dist_{a,b}$为 $a,b$ 两点间的最短距离，那么中转站 $P$ 需要满足 $dist_{S,P}=dist_{P,T}$，而且为了限制小 M 的能力 ，从起点 $S$ 到中转点 $P$ 的路程必须由小 M 徒步行走。

由于咕噜们的计算机珂学家前天刚去世，现在需要你来帮助它们解决小 M 的报告，要求对于小 M 的每一次报告的起点 $S$ 和目标点 $T$，判断是否存在中转点 $P$,使得 $P$ 位于 $S$ 和 $T$ 的正中间。如果存在，输出中转点 $P$ 的标号，以及小 M 需要徒步行走的距离。否则，你只好委婉地拒绝小 M 的请求，输出 -1。

注意： 由于小 M 比较懒，他希望自己走的路程能够尽可能短。所以若有多个 $P$ 点符合条件，请选择让小 M 走的路程最短的点作为 $P$ 点。

由于小 M 将会进行多次长途跋涉，所以他会给出多个询问。

输入格式

第一行一个整数 $n$ 表示树星上城市的数量。
接着 $n-1$ 行，每行两个整数 $u,v$ 表示城市 $u$ 和城市 $v$ 之间存在一条双向道路。
然后是一行一个整数 $q$，表示询问数量。
接着 $q$ 行，每行两个整数 $S,T$，含义如题意所述。

输出格式

共 $q$ 行，每行两个整数 $p,dis$，表示最优的答案为 $p$，并且该点离 $x,y$ 两点的距离为 $dis$。
注意： 若没有满足条件的点，你仅需要输出一行 -1。

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

下面是树星上任意两城市之间的距离：

对于 $5$ 个询问：

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):}$ 无特殊限制。

对于 $100\%$ 的数据，$1 \le n,q \le 10^5$，$1\le x,y,u,v \le n$。