Hierarchy

Krešimir is studying corporate structures, including hierarchies. He observed the employees of a company and their relationships. This problem only considers superior-subordinate relationships, meaning cases where one employee is directly superior to another employee in the company.

A hierarchy is a structure with $N$ employees and $N - 1$ superior-subordinate relationships, where one person is directly or indirectly superior to all employees. The observed company also has $N$ employees and $N - 1$ such relationships, but it is not certain whether it is a valid hierarchy.

Krešimir asked you to help answer this question. He recorded all the data in his notebook. He will also make $Q$ permanent changes by reversing one superior-subordinate relationship, so that the subordinate becomes superior to their former superior. After each change, you must answer the same question: is the current state a valid hierarchy?

The first line contains a positive integer $N$ ($2 \le N \le 3 \cdot 10^5$).

Each of the next $N - 1$ lines contains a pair of integers $p_i$ and $e_i$ ($1 \le p_i, e_i \le N$, $p_i \ne e_i$), meaning that $p_i$ is directly superior to $e_i$, for $i = 1, 2, \dots, N - 1$.

The next line contains a non-negative integer $Q$ ($0 \le Q \le 10^6$).

Each of the following $Q$ lines contains a pair $a_i$, $b_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$). At that moment, $a_i$ is directly superior to $b_i$ or $b_i$ is directly superior to $a_i$.

It is guaranteed that at least one hierarchy can be obtained by some sequence of reversals.

Print $Q + 1$ lines, one for each state (the initial state and the state after each change). Print DA if the current structure is a hierarchy, and NE otherwise.