Hide-And-Seek Game

During the summer vacation, $Serenade$ and $Rhapsody$ are playing hide-and-seek in a park structured as a tree. Each edge of the tree has a weight of 1. $Serenade$ keeps running back and forth between $S_a$ and $T_a$ ($S_a\neq T_a$), while $Rhapsody$ runs back and forth between $S_b$ and $T_b$ ($S_b\neq T_b$). However, $Aria$ doesn't want to run around with them and only wants to know the **earliest** location where $Serenade$ and $Rhapsody$ will meet. Please output the identification number of this location.If they will never meet, output -1.

To be more specific, $Serenade$ starts from $S_a$ and moves one edge towards $T_a$ each time. Once reaching $T_a$, $Serenade$ then moves one edge towards $S_a$ each time. After reaching $S_a$, $Serenade$ moves one edge towards $T_a$ each time, and so on. $Rhapsody$ follows a similar pattern of movement.

Note that this park is quite **mysterious**, so $Serenade$ and $Rhapsody$ will **not meet on an edge** (you can assume that they will choose different paths to traverse the same edge).

The input consists of multiple test cases. The first line contains a single integer $t(1≤t≤500)$ — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ $(2≤n,m≤3 \cdot 10^3)$ — the number of the vertices in the given tree and the number of questions.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$, $u \neq v$) meaning that there is an edge between vertices $u$ and $v$ in the tree.

Each of the next $m$ lines contains four integers $S_a$ , $T_a$ , $S_b$ and $T_b$ ($1\le S_a,T_a,S_b,T_b\le n$, $S_a \neq T_a$ and $S_b \neq T_b$) .

It is guaranteed that the given graph is a tree.

The data guarantees that there will be no more than $20$ groups with a value of $n$ exceeding $400$.

The data guarantees that there will be no more than $20$ groups with a value of $m$ exceeding $400$.

For each test case print a single integer — the identification number of this location which $Serenade$ and $Rhapsody$ will meet or -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

3
6
-1
3

2023“钉耙编程”中国大学生算法设计超级联赛（1）