当前没有测试数据。

题目描述

Here is an unweighted tree (Graph theorem literature) with n vertices along with Q queries. Each query consists of three integers a, b, c. Please find three vertices X, Y, Z such that the distance between X and Y is a, the distance between X and Z is b, and the distance between Y and Z is c.

The distance of two vertices is the number of edges in the simple path between them.

输入格式

The first line of input contains an integer n denoting the number of vertices. The i-th line of the following n-1 lines contains two integers $x_i, y_i$​ denoting an edge connecting vertex $x_i$​ and vertex $y_i$​ (vertices are numbered from 0 to n-1).

The (n+1)-th line contains an integer Q denoting the number of queries. The following Q lines each contains a query represented by three positive integers a, b, c.

• $3 \le n, Q \le 2 \times 10^5$

• $1 \le a,b,c \le n-1$

输出格式

For each query, if there exist three vertices X, Y, Z satisfying that the distance between X and Y is a, the distance between X and Z is b, and the distance between Y and Z is c, output one line containing three numbers indicating the index of X, Y, and Z. If there is no solution, please output only one integer -1 in a line. If there are multiple solutions, output any one.

样例

样例输入 1

5
0 1
2 1
3 1
3 4
4
2 2 2
1 1 1
1 2 3
1 3 1

样例输出 1

0 2 3
-1
3 4 2
-1

样例解释 1

For the first test, the simple path between 0 and 2 is 0-1-2, the simple path between 0 and 3 is 0-1-3, and the simple path between 2 and 3 is 2-1-3. All of them have a distance of 2.