题目描述

鸠和久住在玩游戏。

有一棵以 $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。

8 4
1 2
1 3
2 4
3 5
3 8
5 6
5 7
1 4
1 2
5 2
5 1

NIE
TAK
TAK
TAK

提示

对于所有数据，$1\le n,q\le 1\times 10^6$，$1\le u,v,rt\le n$，$0\le d \le n$。测试点等分。

树随机的方式为，对于 $1<i\le n$ 的 $i$，其父亲在 $[1,i-1]$ 的整数中等概率随机。

树的特殊形态为，以 $1$ 为根，$2i+1$ 的父亲为 $2i-1$，$2i$ 的父亲要么是 $1$ 要么是 $2i-1$。

提示：输入最大大约有 $24$MB，输出最大大约有 $4.76$MB，请选用较快的输入输出方式。在下发文件中有 fastio.cpp，可以使用。

时间限制 $2$s，空间限制 $1024$MB。