동굴 탐험가의 모임 장소

동굴 탐험가 한 무리가 최근 발견된 동굴을 탐사하려고 한다. 동굴은 $1$번부터 $n$번까지 번호가 붙은 $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(폴란드어로 아니오)만 출력한다. 조건을 만족하는 방이 여러 개이면 그중 번호가 가장 작은 방을 출력한다.