Problem Description

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.

Input Format

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 Format

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.

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

Hint

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.

The random tree is generated as follows: for each $i$ with $1<i\le n$, its parent is chosen uniformly at random among the integers in $[1,i-1]$.

The special shape of the tree is as follows: with root $1$, the parent of $2i+1$ is $2i-1$, and the parent of $2i$ is either $1$ or $2i-1$.

Note: the maximum input size is about $24$ MB, and the maximum output size is about $4.76$ MB, so please use fast input/output. The provided file includes fastio.cpp, which you may use.

Time limit: $2$s. Memory limit: $1024$ MB.

Translated by ChatGPT 5