一群洞穴学家计划探索一个新发现的洞穴系统。该洞穴系统包含 $n$ 个编号为 $1$ 到 $n$ 的洞室。这些洞室通过 $n-1$ 条走廊连接，使得任意两个洞室之间都可以互相到达。每条走廊恰好连接两个洞室。

该洞穴将由 $m$ 名洞穴学家进行探索。为方便起见，我们将他们编号为 $1$ 到 $m$。每位洞穴学家都提出了他们想要探索的区域要求。洞穴学家 $i$ 希望从洞室 $a_i$ 开始探索，在洞室 $b_i$ 结束，并且在途中经过最多 $d_i$ 条走廊（重复经过同一条走廊需分别计算）。探险队队长 Byteasar 希望所有的研究人员能在某个时间点在同一个地点会合以交流观察结果。因此，他想知道是否可以选择洞穴系统中的某个洞室，并规划所有洞穴学家的路线，使得他们都能经过所选的洞室。当然，规划的路线必须满足研究人员最初提出的要求。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。 接下来是各个测试用例的描述。每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n, m \le 300\,000$)，分别描述洞穴系统中的洞室数量和洞穴学家的数量。接下来的 $n-1$ 行描述洞穴走廊。每行包含两个整数 $u_i, w_i$ ($1 \le u_i, w_i \le n$)，表示洞室 $u_i$ 和 $w_i$ 之间由一条直接走廊相连。

接下来的 $m$ 行描述洞穴学家的要求。第 $i$ 行包含三个整数 $a_i, b_i, d_i$ ($1 \le a_i, b_i \le n, 1 \le d_i \le 600\,000$)。它们表示洞穴学家 $i$ 将从洞室 $a_i$ 开始探索，在洞室 $b_i$ 结束，且在洞室间移动时经过的走廊总数不超过 $d_i$。你可以假设从洞室 $a_i$ 到 $b_i$ 移动且经过不超过 $d_i$ 条走廊总是可能的。所有测试用例的 $n$ 之和以及 $m$ 的总和均不超过 $300\,000$。

输出格式

你的程序应输出恰好 $t$ 行。第 $i$ 行应包含输入中第 $i$ 个测试用例的答案。如果可以设置洞穴学家的路线，使得他们都能经过同一个洞室，则输出一个单词 TAK（波兰语中的“是”），后跟会合地点的洞室编号。否则，程序应仅输出一个单词：“NIE”。如果存在多个正确答案，输出其中任意一个即可。

样例

样例输入 1

2
5 3
1 2
2 3
2 4
3 5
1 4 2
5 5 5
3 2 1
3 2
1 2
2 3
1 1 2
3 3 1

样例输出 1

TAK 2
NIE