You are given a tree with
nodes, numbered from
to
, connected by
edges. Each edge connects two nodes with the length of
. You're also given
queries. Each query contains three non-negative integers
,
,
.
For each query, you need to find three nodes in the tree, denoted as
,
, and
, such that
,
,
, where
is the length of the simple path from node
to node
. Specially,
.
It is guaranteed that there exists at least one solution for each query. If there are multiple solutions, output any valid solution.
Input Specification
The first line contains one integer
(
), representing the number of nodes in the tree.
Each of the following
lines contain two integers
and
(
), indicating an edge between nodes
and
in the tree.
The nexct line contains one integer
(
), representing the number of queries.
Each of the next
lines contains three integers
,
, and
(
), representing a query.
Output Specification
For each query, output three integers separated by space:
,
, and
, representing the nodes
,
, and
that satisfy the given conditions. There may be multiple valid solutions for each query. You can output any valid solution.
Constraints
The test cases in this problem are not batched.
Points |
Additional constraints |
 |
,  |
 |
,  |
 |
 |
 |
 |
 |
There exists an edge between node and . |
 |
for all queries. |
 |
No additional constraints |
Sample Input
Copy
10
7 10
2 8
10 2
8 1
9 7
4 5
1 6
9 4
4 3
10
3 2 1
5 4 1
6 6 0
3 0 3
1 5 4
2 5 7
6 5 1
2 1 3
2 0 2
2 2 0
Sample Output
Copy
2 6 1
7 6 1
9 6 6
6 2 6
6 1 7
8 6 4
9 6 1
1 2 6
6 8 6
8 6 6
Comments