RoAlgo Contest #7 | joingraf

Traian recently celebrated his birthday and received a graph with $N$ nodes as a gift. Initially, each node was in its own connected component. But then, Traian's dog came and asked him $Q$ questions of the following type:

• $1 \ x \ y$: Add edges to your graph as $(x, x + 1), (x + 1, x + 2), ..., (y - 1, y)$
• $2 \ x \ y$: Tell if nodes $x$ and $y$ are in the same connected component.

Task

Answer Traian's dog's questions.

Input data

The first line of the input contains $N$ and $Q$, representing the number of nodes in the graph and the number of questions, respectively. The next $Q$ lines contain three numbers $t_i, x_i, y_i$, where $t_i$ represents the type of the question, and $x_i$ and $y_i$ are two nodes in the graph.

Output data

For each question of type $2$, output the answer on a new line. The answer can be either Da or Nu (Da for yes and Nu for no in Romanian), depending on the result.

Constraints and clarifications

• $1 \leq N, Q \leq 10^6$
• If an edge has already been added in a question of type $1$, Traian will not add it again.
• For questions of type $2$, it is not guaranteed that $x \leq y$.

Example

stdin

7 6
1 4 7
2 5 3
1 3 6
1 6 7
2 7 1
2 3 4

stdout

Nu
Nu
Da

Explanation

After the first question, the graph will look like this:

The answer to the second question is no, because nodes $3$ and $5$ are not in the same connected component.
After the third question, the graph will look like this:

After the fourth question, the graph will look like this:

The answer to the fifth question is no, because nodes $1$ and $7$ are not in the same connected component.
The answer to the sixth question is yes, because nodes $3$ and $5$ are in the same connected component.