Hide

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?”.

\includegraphics{pathintersection.png}

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 (1n,q2105) —the number of vertices in the tree, and the number of queries, respectively.

The next n1 lines of input contain two integers u and v (1u,vn), 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 (1a,b,c,dn), 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
Hide

Please log in to submit a solution to this problem

Log in