P17440 Water Drops

Jiu and JiuZhu are playing a game. There is a tree rooted at $1$, and there is one drop of water on the tree. Jiu and JiuZhu take turns to move, with Jiu going first. In each move, you may choose a node on the tree that has a water drop, choose some of its children (you cannot choose none), gently remove the drop from this node, split it into several drops, and then gently place them onto the chosen children. It is easy to see that leaves cannot be operated on. When a player cannot make a move, she loses. They like this game very much, so they plan to play many rounds. In each round, they agree on $rt$ and $d$, then wipe all water off the tree, and place exactly one drop of water only on $rt$. Next they start the game. During the game, water drops may only appear at nodes whose distance to $rt$ is $\le d$. Here, the distance between two nodes is the number of edges on the simple path between them. For each round, Jiu wants to know whether she has a winning strategy. Formally, given a rooted tree $T$ with root $1$, define the set of children of node $x$ as $son_x$. For each game round $(rt,d)$, the set of operable nodes is $S=\{x|\text{dis}(x,rt)\le d\}$. Let $A$ be the set of nodes that currently have water drops. Initially, $A=\{rt\}$. Then, each move may choose a node $x$ such that $x\in A$, and choose a **non-empty** set $S'$ such that $S' \subseteq son_x \cap S$, delete $x$ from $A$ and add all elements of $S'$ into $A$. The player who cannot move loses. Determine whether the first player has a winning strategy.

The first line contains two positive integers $n,q$, representing the size of the rooted tree and the number of game rounds. The next $n-1$ lines each contain two positive integers $u,v$, representing an edge of the rooted tree. The next $q$ lines each contain two non-negative integers $rt,d$, representing $rt$ and $d$ in one game round.

Output $q$ lines. The $i$-th line represents the result of the $i$-th game round: if Jiu has a winning strategy, output `TAK`, otherwise output `NIE`.

For all data, $1\le n,q\le 1\times 10^6$, $1\le u,v,rt\le n$, $0\le d \le n$. The test points are evenly distributed. | Test Point ID | n | q | Special Property | | ------------- | ------------------ | ------------------ | ------------------------------ | | $1\sim 2$ | $\le 20$ | $\le 20$ | The tree is guaranteed random. | | $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$ | The tree is guaranteed random. | | $10\sim 12$ | $\le 1\times 10^6$ | $\le 1\times 10^6$ | The tree is guaranteed to have a special shape. | | $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$ | | The random tree is generated as follows: for each $i$ with $1