题目描述

你正在树上玩游戏。

给定一棵 $n$ 个结点的树，有 $Q$ 次询问，每次给定 $x, y, z$，你要找到三个点 $(u, v, w)$ 满足 $\text{dis}(u, v) =x,\text{dis}(u, w) =y,\text{dis}(v, w) =z$ 。其中 $\text{dis}(u, v)$ 表示树上 $u$ 和 $v$ 两点唯一简单路径所包含的边数，$\text{dis}(u, u) = 0$ 。保证有解。

输入格式

第一行一个整数 $n$，表示树的结点树。

接下来 $n−1$ 行每行两个点 $u$ , $v$ 表示一条 $u$ 到 $v$ 的边。

接下来一个整数 $Q$ ，表示询问次数。

接下来 $Q$ 行，每行三个整数 $x, y, z$ 表示一组询问。

输出格式

输出 $Q$ 行，每行三个整数 $u, v, w$ ，满足 $\text{dis}(u, v) =x,\text{dis}(u, w) =y,\text{dis}(v, w) =z$ 。如果多组合法的 $(u, v, w)$ ，输出任意一组，保证有解。

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

数据规模与约定

对于 $10\%$ 的数据，满足 $n, Q≤500$ 。

对于 $20\%$ 的数据，满足 $n, Q≤2×10^3$ 。

对于另外 $20\%$ 的数据，满足 $Q= 1$ 。

对于另外 $20\%$ 的数据，满足 $Q≤10$。

对于另外 $10\%$ 的数据，满足第 $i$ 条边连接 $i$ 和 $i+ 1$ 。

对于另外 $10\%$ 的数据，满足 $x= 0$。

对于 $100\%$的数据，满足 $1≤n, Q≤2×10^5,0≤x, y, z≤2×10^5$。

提示

注意 $x,y,z$ 的意义。（by WBWYX）

不保证 $x+y=z$。（by 一众 20pts loser）