1377: 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 Sa and Ta (Sa ≠ Ta), while Rhapsody runs back and forth between Sb and Tb (Sb ≠ Tb). 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 Sa and moves one edge towards Ta each time. Once reaching
Ta, Serenade then moves one edge towards Sa each time. After reaching Sa, Serenade moves one edge
towards Ta 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 first line of each test case contains two integers n and m (2 ≤ n, m ≤ 3 · 103 ) — 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 ≤ u, v ≤ n, u ≠ v) meaning that there is an edge between vertices u and v in the tree.
Each of the next m lines contains four integers Sa , Ta , Sb and Tb (1 ≤ Sa, Ta, Sb, Tb ≤ n, Sa ≠ Ta and Sb ≠ Tb) .
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
输出
样例输入 Copy
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
样例输出 Copy
3
6
-1
3