题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Bieg na orientację

Bajtazar 正在组织拜托克定向越野赛。比赛将在拜托格勒市的街道上进行。该市的道路网络由 $n$ 个路口组成，通过 $n-1$ 条双向街道连接（从任意路口可以通过街道到达其他任意路口）。

比赛将从起始路口 $v_{1}$ 开始，选手必须先跑到路口 $v_{2}$，那里有任务描述的第一个目标物，然后跑到路口 $v_{3}$，那里有第二个目标物，最后返回起始路口 $v_{1}$。

Bajtazar 正在考虑如何选择路口 $v_{1}, v_{2}, v_{3}$，以使比赛尽可能有趣。其中一个标准是这些路口之间的距离——距离既不能太短（以免选手太容易找到目标物），也不能太长（以免选手因跑步而过于疲惫）。他准备了几个可能的距离方案，并想知道每个方案是否可以通过选择合适的路口实现这些距离。请编写一个程序帮助他解决这个问题。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $q$ $(3 \leq n \leq 300000, 1 \leq q \leq 200000)$，分别表示拜托格勒市的路口数量和距离方案数量。为简化起见，路口编号为从 $1$ 到 $n$ 的整数。

接下来的 $n-1$ 行描述街道：每行包含两个整数 $a$ 和 $b$ $(1 \leq a \neq b \leq n)$，表示编号为 $a$ 和 $b$ 的路口之间有一条双向街道。

接下来的 $q$ 行描述 Bajtazar 考虑的距离方案；每行包含三个整数 $d_{12}, d_{23}, d_{31}$，取值范围为 $[0, n-1]$，分别表示路口 $v_{1}$ 与 $v_{2}$、路口 $v_{2}$ 与 $v_{3}$ 以及路口 $v_{3}$ 与 $v_{1}$ 之间的距离。有时 Bajtazar 会考虑距离为零的情况（此时某些路口可能重复）。

输出格式

输出应包含恰好 $q$ 行，分别对应输入中的各个查询。答案为以下两种之一：如果所需的三路口组合不存在，则输出 NIE；如果存在，则输出 TAK，后面跟着三个整数 $v_{1}, v_{2}, v_{3}$。

如果存在多个解，你的程序可以输出其中任意一个。

6 4
1 2
2 3
2 5
2 4
5 6
3 2 3
1 2 3
1 1 1
3 0 3

TAK 6 4 3
TAK 4 2 6
NIE
TAK 4 6 6

附加样例

1. $n=10$，$q=10$；
2. $n=7$，$q=343$；路径形状，所有可能的查询；
3. $n=1000$，$q=1000$；长度为 $500$ 的“毛虫”形状，节点 $1,3,\ldots,499$ 各连接两个额外节点；
4. $n=300000$，$q=200000$；所有方案中 $d_{12}=0$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

如果你的程序在回答 TAK 时输出的路口编号不正确或未输出编号，仍可获得该测试点 $50\%$ 的分数。