Problem M
Path Intersection
You are given an undirected tree on
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
The next
The next
Output
For each query, if there is no intersection between the
given paths, print
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 |