{"raw_statement":[{"iden":"statement","content":"你正在树上玩游戏。\n\n给定一棵 $n$ 个结点的树，有 $Q$ 次询问，每次给定 $x, y, z$，你要找到三个点 $(u, v, w)$ 满足 $\\operatorname{dis}(u, v) =\nx, \\operatorname{dis}(u, w) = y, \\operatorname{dis}(v, w) = z$。其中 $\\operatorname{dis}(u, v)$ 表示树上 $u$ 和 $v$ 两点唯一简单路径所包含的边数，$\\operatorname{dis}(u, u) = 0$。\n保证有解。\n"},{"iden":"input","content":"第一行一个整数 $n$，表示树的结点数。\n\n接下来 $n - 1$ 行每行两个点 $u, v$ 表示一条 $u$ 到 $v$ 的边。\n\n接下来一个整数 $Q$，表示询问次数。\n\n接下来 $Q$ 行，每行三个整数 $x, y, z$ 表示一组询问。"},{"iden":"output","content":"输出 $Q$ 行，每行三个整数 $u, v, w$，满足 $\\operatorname{dis}(u, v) = x, \\operatorname{dis}(u, w) = y, \\operatorname{dis}(v, w) = z$。如果多组合法的\n$(u, v, w)$，输出任意一组，保证有解。\n"},{"iden":"note","content":"对于 10% 的数据，满足 $n, Q ≤ 500$。\n\n对于 20% 的数据，满足 $n, Q ≤ 2 \\times 10^3$。\n\n对于另外 20% 的数据，满足 $Q = 1$。\n\n对于另外 20% 的数据，满足 $Q \\le 10$。\n\n对于另外 10% 的数据，满足第 $i$ 条边连接 $i$ 和 $i + 1$。\n\n对于另外 10% 的数据，满足 $x = 0$。\n\n对于 100% 的数据，满足 $1 ≤ n, Q ≤ 2 \\times 10^5, 0 ≤ x, y, z ≤ 2 \\times 10^5$。\n\n下发 checker 和 checker.exe，分别用于 64 位 linux 以及 windows 下的答案校验。\n\n你可以使用 `./checker < 输入文件名 > < 输出文件名 > < 答案文件名 >` 来检测你的输出文件是否合\n法。\n\n实际上下发的 checker 并不会用到答案文件，所以你只需要随便选择一个文件作为答案文件即可。\n\n你需要保证输入文件合法，即格式正确并且有解，否则可能会出现未知错误。\n\n根据你的输出文件的问题，checker 分别会返回一下信息：\n\n1. 如果你的输出文件正确，则 checker 会返回 `Accepted!`。\n2. 如果在第 $t$ 组数据，答案错误，则 checker 会返回 `Wrong answer on test t!`。\n3. 如果你的格式错误，则 checker 会返回 `wrong output format` 后接相关错误信息。\n\nUPD: 在洛谷下发 chk.cpp。"}],"translated_statement":null,"sample_group":[["10\n7 10\n2 8\n10 2\n8 1\n9 7\n4 5\n1 6\n9 4\n4 3\n10\n3 2 1\n5 4 1\n6 6 0\n3 0 3\n1 5 4\n2 5 7\n6 5 1\n2 1 3\n2 0 2\n2 2 0","2 6 1\n7 6 1\n9 6 6\n6 2 6\n6 1 7\n8 6 4\n9 6 1\n1 2 6\n6 8 6\n8 6 6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}