32534번 - Hijerarhija 서브태스크다국어

문제

Krešimir has started studying corporate structures, including hierarchies. He observed employees and their relationships within a company. In this case, we are only looking at superior–subordinate relationships, meaning relationships 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 there is one person who is directly or indirectly superior to all employees. In the observed company, there are also $N$ employees and $N - 1$ such relationships, but it is not certain whether this is a valid hierarchy or not.

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

입력

In the first line, there is a positive integer $N$ (2ドル ≤ N ≤ 3 \cdot 10^5$).

In the next $N - 1$ lines, for each $i = 1, 2, \dots , N - 1,ドル there is a pair of integers $p_i$ and $e_i$ (1ドル ≤ p_i , e_i ≤ N,ドル $p_i \ne e_i$), indicating that $p_i$ is directly superior to $e_i$.

In the next line, there is a non-negative integer $Q$ (0ドル ≤ Q ≤ 10^6$).

In the following $Q$ lines, there are pairs $a_i,ドル $b_i$ (1ドル ≤ a_i , b_i ≤ N,ドル $a_i \ne b_i$). It is guaranteed that at that moment, $a_i$ will either be directly superior to $b_i$ or vice versa.

In the test data, it is guaranteed that it will be possible to achieve at least one hierarchy with some sequence of reversals.

출력

In the next $Q + 1$ lines, for each of the given scenarios, it is necessary to output whether the current structure is a hierarchy, i.e., "DA" if it is, or "NE" if it is not (without quotation marks).

제한

서브태스크

힌트