题目背景

译自 COCI 2024/2025 #1 T3。$\texttt{3s,0.5G}$。满分为 $90$。

题目描述

有 $n$ 个节点，给定 $(n-1)$ 对点之间的父子关系。

有 $m$ 个修改，每次给定一对父子，将它们的关系反转（即，原来的父亲变成儿子，儿子变成父亲）。

在第一次修改前，和每次修改后，输出这张图是否是一棵有根树。

输入格式

第一行，一个正整数 $n$。

接下来 $(n-1)$ 行，每行两个正整数 $u,v$，表示 $u$ 是 $v$ 的父亲。

接下来一行，一个正整数 $m$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示一次修改。保证 $u,v$ 是父子关系。

输出格式

输出 $(m+1)$ 行：

在对应时刻，若是有根树，输出 $\texttt{DA}$（克罗地亚语「是」）；否则输出 $\texttt{NE}$（克罗地亚语「否」）。

保证至少有一个回答是 $\texttt{DA}$。

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

DA
DA
DA
DA

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

DA
NE
DA
DA
NE

提示

对于 $100\%$ 的数据，保证：

• $2\le n\le 3\times 10^5$；
• $0\le m\le 10^6$；
• $1\le u,v\le n$，$u\neq v$。
• 至少有一个回答是 $\texttt{DA}$。

• 特殊性质 A：$m=0$。
• 特殊性质 B：对于 $\forall 1\le i\lt n$，$(i,i+1)$ 间有父子关系。