Krešimir 开始研究公司结构，包括层级结构。他观察了公司内部员工及其关系。在这种情况下，我们只关注上下级关系，即一名员工直接隶属于另一名员工的关系。

层级结构是一种包含 $N$ 名员工和 $N-1$ 条上下级关系的结构，其中有一人直接或间接地是所有其他员工的上级。在所观察的公司中，也有 $N$ 名员工和 $N-1$ 条这样的关系，但不确定这是否是一个有效的层级结构。

Krešimir 请你帮忙回答这个问题。他记录了笔记本中的所有数据。此外，他将在笔记本中进行 $Q$ 次永久性更改，每次更改都会反转一条上下级关系，使得下属变为其原上级的上级。在每次更改后，都需要回答同一个问题：当前状态是否是一个有效的层级结构？

输入格式

第一行包含一个正整数 $N$ ($2 \le N \le 3 \cdot 10^5$)。

接下来的 $N-1$ 行，对于每个 $i = 1, 2, \dots, N-1$，包含一对整数 $p_i$ 和 $e_i$ ($1 \le p_i, e_i \le N, p_i \neq e_i$)，表示 $p_i$ 直接是 $e_i$ 的上级。

下一行包含一个非负整数 $Q$ ($0 \le Q \le 10^6$)。

接下来的 $Q$ 行，包含一对整数 $a_i, b_i$ ($1 \le a_i, b_i \le N, a_i \neq b_i$)。保证在此时，$a_i$ 要么直接是 $b_i$ 的上级，要么反之。

在测试数据中，保证通过某种反转序列，至少可以达到一个层级结构。

输出格式

在接下来的 $Q+1$ 行中，对于每个给定的场景，需要输出当前结构是否为层级结构，即如果是，则输出 "DA"，如果不是，则输出 "NE"（不含引号）。

子任务

样例

输入 1

3
1 2
1 3
3
1 2
1 2
1 3

输出 1

DA
DA
DA
DA

输入 2

4
2 1
2 3
1 4
4
4 1
4 1
3 2
1 4

输出 2

DA
NE
DA
DA
NE

Figure 1. 层级结构示意图