#5062.「POI2017 R3」米达斯 Midas

题目描述

Bajtazar，米达斯国王的御用工程师，奉命建造了一座迷宫。原计划迷宫的房间用于展示珍奇展品，但实际上，它成了为国王金库增收巨额金币的工具。

迷宫由 $n$ 个房间和连接它们的通道组成，入口位于房间 $1$。每间房间的通道分叉，可选择左或右通道离开（部分通道可能被封锁，无法通行）。通道只分叉，不汇合。游客携带收费装置，每次通过通道需支付金币，费用取决于已付金币总数及所选通道：左通道费用等于此前总费用，右通道费用比此前总费用多 $1$ 金币。

这种复杂的收费机制旨在掩盖实际游览成本，但给游客带来不便。Bajtazar 决定协助游客，聘请你编写程序回答以下查询：若游客持有恰好从入口到房间 $x$ 所需的金币，能否用同样金币从入口到达房间 $y$？

输入格式

第一行包含一个正整数 $n$，表示迷宫房间数量，房间编号为 $1$ 至 $n$，入口位于房间 $1$。

接下来的 $n$ 行描述迷宫，第 $i$ 行包含两个整数 $l_i, r_i$ ($0 \leq l_i, r_i \leq n$)。若 $l_i > 0$，表示从房间 $i$ 的左通道可达房间 $l_i$；若 $l_i = 0$，左通道被封锁。$r_i$ 类似描述右通道。从房间 $1$ 出发，可达所有其他房间。

下一行包含一个正整数 $z$，表示查询数量。

接下来的 $z$ 行描述查询，第 $i$ 行包含两个整数 $x_i, y_i$ ($1 \leq x_i, y_i \leq n$)，表示查询：从入口到房间 $x_i$ 所需金币是否足够到达房间 $y_i$。

输出格式

输出 $z$ 行，若第 $i$ 个查询的答案为是，在第 $i$ 行输出 TAK，否则输出 NIE。

样例

输入

12
3 9
0 4
2 5
0 0
6 0
7 8
0 0
0 0
10 12
11 0
0 0
0 0
6
11 8
8 6
11 7
1 2
4 10
3 3

输出

NIE
TAK
TAK
TAK
NIE
TAK

数据范围与提示

详细子任务附加限制及分值如下表所示。