Problem Description

You are playing a game on a tree.

You are given a tree with $n$ nodes and $Q$ queries. For each query, you are given $x, y, z$, and you need to find three nodes $(u, v, w)$ such that $\operatorname{dis}(u, v) = x$, $\operatorname{dis}(u, w) = y$, and $\operatorname{dis}(v, w) = z$. Here, $\operatorname{dis}(u, v)$ denotes the number of edges on the unique simple path between nodes $u$ and $v$ in the tree, and $\operatorname{dis}(u, u) = 0$.

It is guaranteed that a solution exists.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

The next $n - 1$ lines each contain two nodes $u, v$, representing an edge between $u$ and $v$.

The next line contains an integer $Q$, the number of queries.

The next $Q$ lines each contain three integers $x, y, z$, representing one query.

Output Format

Output $Q$ lines. Each line should contain three integers $u, v, w$ such that $\operatorname{dis}(u, v) = x$, $\operatorname{dis}(u, w) = y$, and $\operatorname{dis}(v, w) = z$. If there are multiple valid triples $(u, v, w)$, output any one of them. It is guaranteed that a solution exists.

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

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

Hint

For $10\%$ of the testdata, $n, Q \le 500$.

For $20\%$ of the testdata, $n, Q \le 2 \times 10^3$.

For another $20\%$ of the testdata, $Q = 1$.

For another $20\%$ of the testdata, $Q \le 10$.

For another $10\%$ of the testdata, the $i$-th edge connects $i$ and $i + 1$.

For another $10\%$ of the testdata, $x = 0$.

For $100\%$ of the testdata, $1 \le n, Q \le 2 \times 10^5$ and $0 \le x, y, z \le 2 \times 10^5$.

A checker and checker.exe are provided, for checking answers on 64-bit Linux and Windows, respectively.

You can use ./checker < input file name > < output file name > < answer file name > to check whether your output file is valid.

In fact, the provided checker will not use the answer file, so you can choose any file as the answer file.

You need to ensure that the input file is valid, meaning the format is correct and a solution exists. Otherwise, unknown errors may occur.

Depending on the problems in your output file, the checker will return the following messages:

1. If your output file is correct, the checker will return Accepted!.
2. If the answer is wrong on test $t$, the checker will return Wrong answer on test t!.
3. If your format is incorrect, the checker will return wrong output format followed by related error information.

UPD: On Luogu, chk.cpp is provided.

Translated by ChatGPT 5