U509532 [COCI2024/2025 #1] Hijerarhija

Krešimir 开始研究企业结构，包括“层级制度”。他观察了员工以及他们在公司内的关系。在这个例子中，我们只关注“上下级关系”，即一个员工在公司中直接高于另一个员工的关系。 等级制度是一种具有 $N$ 名员工和 $N-1$ 个上下级关系的结构，其中有一人是所有员工的直接或间接上级。在所观察的公司中，也有 $N$ 名员工和 $N-1$ 个这样的关系，但不确定这是否是一个有效的等级制度。 Krešimir 要求你帮助回答这个问题。他在笔记本中记录了所有数据。此外，在他的笔记本中，他将通过逆转一个上下级关系来永久改变 $Q$，使得下级成为他们之前上级的上级。每次这样的改变后，都需要回答同样的问题：当前状态是一个有效的等级吗?

第一行输入一个正整数 $N$。 在接下来的 $N-1$ 行中，对于每个 $i=1,2,\dots.N-1$，存在一对整数 $p_i$和 $e_i$，这表明 $p_i$ 直接优于 $e_i$。 接下来的 $N+1$ 行，有一个非负整数 $Q$。 在接下来的 $Q$ 行中，有对数 $(a_i,b_i)$。可以保证在那一刻，$a_i$ 要么直接优于 $b_i$，要么反之。 在测试数据中，可以**保证**实现至少一个具有某种逆序的层次结构。

输出 $Q+1$ 行，对于每个给定的场景，有必要输出当前结构是否为层次结构，即如果为是输出 `DA`，否则输出 `NE`。

对于 $100\%$ 的数据，保证 $2\le p_i,e_i,a_i,b_i\le N\le3\times10^5$，$0\le Q\le10^6$。 | Substask | 分数 | 约束条件 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | | $1$ | $7$ | $N\le300,Q=0$ | | $2$ | $12$ | $N,Q\le300$ | | $3$ | $16$ | $N,Q\le1000$ | | $4$ | $15$ | $Q=0$ | | $5$ | $23$ | 对于每个 $i=1,2,\dots,N-1$，它将认为 $i$ 直接优于 $i+1$，反之亦然。 | | $6$ | $17$ | 无 |