#4151. [AMPPZ2014]The Cave

内存限制:256 MiB 时间限制:5 Sec

题目描述

给定一棵有n个节点的树,相邻两点之间的距离为1。
请找到一个点x,使其满足所有m条限制,其中第i条限制为dist(x,a[i])+dist(x,b[i])<=d[i]。

输入格式

第一行包含一个正整数t(1<=t<=1000),表示数据组数。
对于每组数据,第一行包含两个正整数n,m(2<=n,m<=300000),表示点数、限制数。
接下来n-1行,每行两个正整数x,y(1<=x,y<=n),表示树上的一条边。
接下来m行,每行三个正整数a[i],b[i],d[i](1<=a[i],b[i]<=n,1<=d[i]<=600000),描述一条限制。
输入数据保证所有n之和不超过300000,所有m之和也不超过300000。

输出格式

输出t行。第i行输出第i组数据的答案,如果无解输出NIE,否则输出TAK,
然后输出x,如有多组解,输出任意一组。

样例

样例输入


			
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

样例输出


			
TAK 2
NIE

数据范围与提示