The Cave

A group of speleologists plans to explore a recently discovered cave complex. The cave complex consists of $n$ chambers numbered from $1$ to $n$. The chambers are connected by $n-1$ corridors in such a way that any chamber can be reached from any other. Each corridor connects exactly two chambers.

The cave will be explored by a group of $m$ speleologists, numbered from $1$ to $m$. Each speleologist has stated the area of the cave he wants to explore. Speleologist $i$ wants to begin his exploration in chamber $a_i$, finish in chamber $b_i$, and traverse at most $d_i$ corridors on his way (every pass through a corridor is counted separately, even when the same corridor is used again). Byteasar, the head of the expedition, wants all the researchers to meet at some point in time to exchange their observations. He is wondering whether he can choose one chamber of the cave and plan the routes of all speleologists so that every route passes through the selected chamber. The planned routes must meet the requirements stated by the researchers.

The first line contains one integer $t$ ($1 \le t \le 1000$), the number of test cases. The descriptions of the test cases follow. The description of a single test case begins with a line containing two integers $n$ and $m$ ($2 \le n, m \le 300\,000$), the number of chambers in the cave and the number of speleologists. The next $n-1$ lines describe the corridors. Each of them contains two integers $u_i$ and $w_i$ ($1 \le u_i, w_i \le n$), meaning that chambers $u_i$ and $w_i$ are connected by a direct corridor.

The next $m$ lines describe the speleologists' requirements. The $i$-th of these lines contains three integers $a_i$, $b_i$, $d_i$ ($1 \le a_i, b_i \le n$, $1 \le d_i \le 600\,000$): speleologist $i$ begins in chamber $a_i$, finishes in chamber $b_i$, and passes through at most $d_i$ corridors while moving between chambers. It is guaranteed that chamber $b_i$ can be reached from chamber $a_i$ by traversing at most $d_i$ corridors. The sum of $n$ over all test cases and the sum of $m$ over all test cases each do not exceed $300\,000$.

Print exactly $t$ lines. The $i$-th line contains the answer to the $i$-th test case. If the routes can be planned so that they all pass through one common chamber, print the word TAK (Polish for yes) followed by a space and the number of the chamber where the meeting takes place. Otherwise print only the word NIE (Polish for no). If several chambers are valid meeting places, print the one with the smallest number.