# 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.

Sample Input 1 | Sample Output 1 |
---|---|

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 |