## Three Nodes

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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.

,
,
There exists an edge between node and .
for all queries.

#### Sample Input

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

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