hijerarhija (COCI CONTEST_#1)
Time limit: 3 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: data structures, dynamic graph, graph theory, tree

# Task Hijerarhija

Croatian Open Competition in Informatics  
Round 1, October 5th 2024

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.

![](./_page_0_Picture_4.jpeg)

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?

## Input

In the first line, there is a positive integer *N* (2 ≤ *N* ≤ 3 ⋅ 10<sup>5</sup>).

In the next *N* - 1 lines, for each *i* = 1, 2, ..., *N* - 1, there is a pair of integers *p<sub>i</sub>* and *e<sub>i</sub>* (1 ≤ *p<sub>i</sub>*, *e<sub>i</sub>* ≤ *N*, *p<sub>i</sub>* ≠ *e<sub>i</sub>*), indicating that *p<sub>i</sub>* is directly superior to *e<sub>i</sub>*.

In the next line, there is a non-negative integer *Q* (0 ≤ *Q* ≤ 10<sup>6</sup>).

In the following *Q* lines, there are pairs *a<sub>i</sub>*, *b<sub>i</sub>* (1 ≤ *a<sub>i</sub>*, *b<sub>i</sub>* ≤ *N*, *a<sub>i</sub>* ≠ *b<sub>i</sub>*). It is guaranteed that at that moment, *a<sub>i</sub>* will either be directly superior to *b<sub>i</sub>* 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.

## Output

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).

## Scoring

| Subtask | Points | Constraints                                                                 |
| :-------: | :-----: | :-------------------------------------------------------------------------- |
| 1       | 7     | *N* ≤ 300, *Q* = 0                                                         |
| 2       | 12    | *N*, *Q* ≤ 300                                                             |
| 3       | 16    | *N*, *Q* ≤ 1000                                                            |
| 4       | 15    | *Q* = 0                                                                    |
| 5       | 23    | For each *i* = 1, 2, ..., *N* - 1, it will hold that *i* is directly superior to *i* + 1 or vice versa. |
| 6       | 17    | No additional constraints.                                                 |

![](./_page_1_Picture_0.jpeg)

## Examples

| Input | Input |
| :---- | :---- |
| 3     | 4     |
| 1 2   | 2 1   |
| 1 3   | 2 3   |
|       | 1 4   |
| 3     | 4     |
| 1 2   | 4 1   |
| 1 2   | 4 1   |
| 1 3   | 3 2   |
|       | 1 4   |
| Output| Output|
| DA    | DA    |
| DA    | NE    |
| DA    | DA    |
| DA    | DA    |
|       | NE    |

Starter code:

Grader code:

Setup script:

Evaluation script: