P17440 水滴

鸠和久住在玩游戏。 有一棵以 $1$ 为根的树，树上有一滴水。鸠和久住轮流操作，鸠先手。每轮操作可以选择树上一个有水滴的节点，选择它的某些儿子，**不能不选**，把这个节点上的水滴轻轻移开，分裂成若干滴水滴，再轻轻放到选中的儿子上。容易发现叶子无法操作。当某个人不能操作的时候，她就输了。 她们十分喜欢这个游戏，于是打算玩很多次。每一次，她们会约定 $rt$ 和 $d$，然后把树上的所有水全部擦干，仅往 $rt$ 上放上一滴水。接下来她们开始游戏，游戏过程中水滴只能出现在离 $rt$ 的距离 $\le d$ 的点上。在这里，两点之间的距离看作它们之间的简单路径的边数。对于每一轮游戏，鸠想知道，她是否有必胜策略。 形式化地，给定以 $1$ 为根的有根树 $T$，定义点 $x$ 的儿子集合为 $son_x$。对于每一轮游戏 $(rt,d)$，可操作的点集为 $S=\{x|\text{dis}(x,rt)\le d\}$。定义有水滴的集合的点集为 $A$。一开始 $A=\{rt\}$，接下来每一次操作可以选择点 $x$，满足 $x\in A$，再选择一个**非空**集合 $S'$，满足 $S' \subseteq son_x \cap S$，把 $x$ 从 $A$ 中删除并把 $S'$ 中的所有元素加入 $A$ 中，不能操作的人输。求先手有没有必胜策略。

第一行两个正整数 $n,q$，分别表示有根树的大小和游戏的次数。 接下来 $n-1$ 行，每行两个正整数 $u,v$，表示了有根树的一条边。 接下来 $q$ 行，每行两个非负整数 $rt,d$，表示一轮游戏中的 $rt$ 和 $d$。

共 $q$ 行，第 $i$ 行表示第 $i$ 轮游戏的结果，如果鸠有必胜策略输出 `TAK`，否则输出 `NIE`。

对于所有数据，$1\le n,q\le 1\times 10^6$，$1\le u,v,rt\le n$，$0\le d \le n$。测试点等分。 | 测试点编号 | n | q | 特殊性质 | | ----------- | ------------------ | ------------------ | ---------------- | | $1\sim 2$ | $\le 20$ | $\le 20$ | 保证树随机 | | $3\sim 4$ | $\le 2000$ | $\le 2000$ | | | $5\sim 6$ | $\le 1\times 10^6$ | $\le 20$ | | | $7\sim 9$ | $\le 1\times 10^6$ | $\le 1\times 10^6$ | 保证树随机 | | $10\sim 12$ | $\le 1\times 10^6$ | $\le 1\times 10^6$ | 保证树有特殊形态 | | $13\sim 16$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | | | $17\sim 18$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | | | $19\sim 20$ | $\le 1\times 10^6$ | $\le 1\times 10^6$ | | 树随机的方式为，对于 $1