题目描述

给定一棵有 $n$ 个节点的树，相邻两点之间的距离为 $1$。

请找到一个点 $x$，使其满足所有 $m$ 条限制，其中第 $i$ 条限制为 $dis(x,a_i)+dis(x,b_i)\leq d_i$，其中 $dis(u,v)$ 表示树上 $u,v$ 两点间最短路径的长度。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行包含两个正整数 $n,m$，表示点数、限制数。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示树上的一条边。

接下来 $m$ 行，每行三个正整数 $a_i,b_i,d_i$，描述一条限制。

输出格式

输出 $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

数据规模与约定

对于 $100\%$ 的数据，$1\leq T\leq 10^3$，$1\leq \sum n,\sum m\leq 3\times 10^5$，$n,m\ge 2$，$1\leq x,y,a_i,b_i\leq n$，$1\leq d_i\leq 6\times 10^5$。

SPJ 未配置。