暑假期间，Serenade 和 Rhapsody 在一个树状结构的公园里玩捉迷藏。树的每条边权重均为 1。Serenade 在 $S_a$ 和 $T_a$ ($S_a \neq T_a$) 之间往返奔跑，而 Rhapsody 在 $S_b$ 和 $T_b$ ($S_b \neq T_b$) 之间往返奔跑。然而，Aria 不想和他们一起跑，只想知道 Serenade 和 Rhapsody 最早会在哪个位置相遇。请输出该位置的编号。如果他们永远不会相遇，则输出 -1。

具体来说，Serenade 每次从 $S_a$ 出发，向 $T_a$ 方向移动一条边。到达 $T_a$ 后，Serenade 每次向 $S_a$ 方向移动一条边。到达 $S_a$ 后，Serenade 再次向 $T_a$ 方向移动一条边，依此类推。Rhapsody 遵循类似的移动模式。

注意，这个公园非常神秘，因此 Serenade 和 Rhapsody 不会在边上相遇（你可以假设他们会选择不同的路径来经过同一条边）。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 500$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n, m \le 3 \cdot 10^3$)，分别表示给定树的顶点数和询问次数。

接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示树中顶点 $u$ 和 $v$ 之间有一条边。

接下来的 $m$ 行，每行包含四个整数 $S_a, T_a, S_b$ 和 $T_b$ ($1 \le S_a, T_a, S_b, T_b \le n, S_a \neq T_a$ 且 $S_b \neq T_b$)。

保证给定的图是一棵树。

数据保证 $n$ 超过 400 的组数不超过 20 组。

数据保证 $m$ 超过 400 的组数不超过 20 组。

输出格式

对于每个测试用例，输出一个整数，表示 Serenade 和 Rhapsody 相遇的位置编号，如果无法相遇则输出 -1。

样例

输入 1

1
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

输出 1

3
6
-1
3