[AMPPZ2014]The Cave
时间限制：5s 空间限制：256MB
题目描述
给定一棵有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
提示
没有写明提示
题目来源
鸣谢Claris上传