계층 구조

크레시미르는 계층 구조를 포함한 기업 구조를 공부하고 있다. 그는 회사의 직원들과 그들 사이의 관계를 관찰했다. 이 문제에서는 한 직원이 다른 직원의 직속 상사인 상사-부하 관계만 다룬다.

계층 구조는 직원 $N$명과 상사-부하 관계 $N - 1$개로 이루어진 구조로, 한 사람이 직접 또는 간접적으로 모든 직원의 상사인 구조다. 관찰한 회사에도 직원 $N$명과 그런 관계 $N - 1$개가 있지만, 이것이 올바른 계층 구조인지는 확실하지 않다.

크레시미르는 이 질문에 답하도록 도움을 요청했다. 그는 모든 자료를 노트에 기록했다. 또한 상사-부하 관계 하나를 뒤집어서 부하가 기존 상사의 상사가 되도록 하는 변경을 노트에서 $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 \ne 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 \ne b_i$)가 주어진다. 그 시점에 $a_i$가 $b_i$의 직속 상사이거나, 그 반대이다.

뒤집기를 몇 번 거쳐 계층 구조를 하나 이상 만들 수 있다고 보장된다.

$Q + 1$개 줄을 출력한다. 각 상태(초기 상태와 변경할 때마다의 상태)에 대해 현재 구조가 계층 구조이면 DA, 아니면 NE를 출력한다.