Migrated from Lutece 3261 野猫绝赞散步中

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

野猫正带着她的猫猫大军散步。

假定要乐奈的活动区域构成了一棵树，这棵树上有 $n$ 个结点。经过任意一条边所需要的时间是相同的。

那么野猫的活动路径是从 $s_a$ 出发走到 $t_a$，然后再从 $t_a$ 走到 $s_a$，如此循环往复。

为了把流浪猫抓回去，爱音打算从 $s_b$ 出发走到 $t_b$，然后再从 $t_b$ 走到 $s_b$，如此循环往复。

由于不知道野猫的位置，爱音斯坦博士（？）打算进行多次查询。每次都会给出 $s_a,t_a,s_b,t_b$，而你的任务就是计算出爱音和乐奈最早相遇的位置。如果她们不能相遇，输出 -1。

（注：她们只能在结点处相遇，而不能在边上相遇。你可以认为要乐奈总是会走神秘的小道，导致她们无法在路上相遇。）

Input

第一行输入两个整数 $n,m$。 接下来 $n-1$ 行每行输入两个整数 $u_i, v_i$，表示第 $i$ 条边连接 $u_i$ 和 $v_i$ 两个点。 接下来 $m$ 行每行输入四个整数 $s_a,t_a,s_b,t_b$，表示一次询问。

Output

输出 $m$ 行，每行一个整数，表示第 $i$ 次询问的结果。

Samples

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

3
6
-1
3

Constraints

$2\leq n,m \leq 3\times 10^3$。 $1\leq u_i,v_i \leq n,u_i \neq v_i$，保证图是一棵树。 $1\leq s_a,t_a,s_b,t_b \leq n$ 且 $s_a \neq t_a,s_b \neq t_b$。

Resources

2024 UESTC ICPC Training for Math