树链还是简单一点好
题目描述
银河系有一个树星。
众所周知，树星的道路是树形结构，也就是说，如果树星上一共有 nnn 座城市，那么就存在 n−1n-1n−1 条双向道路使得各个城市间相互连通，并且默认每条道路的长度为 111。
小 M 是树星的一只咕噜，最近它偶然获得了一台来自人类的超空间穿梭机。
这台机器非常奇妙，只要你确定了一个目标地点，你便可以使用该机器迅速地穿梭过去。由于这台机器十分 BUG，于是树星的咕噜们便制定了限制穿梭的规则，规定小 M 必须在中转站才能使用穿梭机，而当小 M 要求使用穿梭机时，必须征得他们的同意。
具体规则如下，假定起点为 SSS，小 M 首先确定一个目标地点 TTT，然后报告树星的咕噜们，它们会为小 M 确定一个中转站 PPP,这个中转站必须位于 SSS 和 TTT 的正中间。若设 dista,bdist_{a,b}dista,b为 a,ba,ba,b 两点间的最短距离，那么中转站 PPP 需要满足 distS,P=distP,Tdist_{S,P}=dist_{P,T}distS,P=distP,T，而且为了限制小 M 的能力 ，从起点 SSS 到中转点 PPP 的路程必须由小 M 徒步行走。
由于咕噜们的计算机珂学家前天刚去世，现在需要你来帮助它们解决小 M 的报告，要求对于小 M 的每一次报告的起点 SSS 和目标点 TTT，判断是否存在中转点 PPP,使得 PPP 位于 SSS 和 TTT 的正中间。如果存在，输出中转点 PPP 的标号，以及小 M 需要徒步行走的距离。否则，你只好委婉地拒绝小 M 的请求，输出 -1。
注意： 由于小 M 比较懒，他希望自己走的路程能够尽可能短。所以若有多个 PPP 点符合条件，请选择让小 M 走的路程最短的点作为 PPP 点。
由于小 M 将会进行多次长途跋涉，所以他会给出多个询问。
输入格式
第一行一个整数 nnn 表示树星上城市的数量。
接着 n−1n-1n−1 行，每行两个整数 u,vu,vu,v 表示城市 uuu 和城市 vvv 之间存在一条双向道路。
然后是一行一个整数 qqq，表示询问数量。
接着 qqq 行，每行两个整数 S,TS,TS,T，含义如题意所述。
输出格式
共 qqq 行，每行两个整数 p,disp,disp,dis，表示最优的答案为 ppp，并且该点离 x,yx,yx,y 两点的距离为 disdisdis。
注意： 若没有满足条件的点，你仅需要输出一行 -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
下面是树星上任意两城市之间的距离：
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
对于 555 个询问：
222 离 1,31,31,3 的距离均为 111。
111 离 2,52,52,5 的距离均为 111。
111 离 7,47,47,4 的距离均为 222。
888 离 8,88,88,8 的距离均为 000。
没有点离 1,51,51,5 的距离相同。
数据规模与约定
Subtask 1(30 pts): n,q≤2×103\texttt{Subtask 1(30 pts): } n,q \le 2 \times 10^3Subtask 1(30 pts): n,q≤2×103。
Subtask 2(10 pts):\texttt{Subtask 2(10 pts):}Subtask 2(10 pts): 所有询问均满足 x=yx=yx=y。
Subtask 3(10 pts):\texttt{Subtask 3(10 pts):}Subtask 3(10 pts): 所有询问均满足 x=1x=1x=1。
Subtask 3(50 pts):\texttt{Subtask 3(50 pts):}Subtask 3(50 pts): 无特殊限制。
对于 100%100\%100% 的数据，1≤n,q≤1051 \le n,q \le 10^51≤n,q≤105，1≤x,y,u,v≤n1\le x,y,u,v \le n1≤x,y,u,v≤n。