Problem M
Path Intersection

You are given an undirected tree on $n$ vertices. You need to answer $q$ queries of the form “What is the intersection of the path from $a$ to $b$, and the path from $c$ to $d$?”.

If the intersection is empty, print -1. Otherwise, notice that the intersection will always be a path, so print its endpoints.

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n, q \le 2\cdot 10^5$) —the number of vertices in the tree, and the number of queries, respectively.

The next $n-1$ lines of input contain two integers $u$ and $v$ ($1 \le u, v \le n$), representing an undirected edge between $u$ and $v$. It is guaranteed that the edges given by these lines form a tree.

The next $q$ lines of input contain four integers $a$, $b$, $c$, and $d$ ($1 \le a, b, c, d \le n$), indicating a query as described above.

Output

For each query, if there is no intersection between the given paths, print $-1$. Otherwise, print two integers —the endpoints of the intersection path.

12 7
1 2
3 1
2 4
5 3
6 3
3 7
6 8
9 6
8 10
8 11
12 11
10 7 2 12
12 7 11 11
2 2 4 4
2 11 2 11
4 6 8 12
5 9 10 7
5 4 7 10

3 8
11 11
-1
11 2
-1
3 6
3 3