/*
 * =====================================================================================
 *
 *       Filename:  IA_Disjoint_data_set.cpp
 *
 *    Description:  Se dau N multimi de numere, initial fiecare multime i continand un 
 singur element, mai exact elementul i. Asupra acestor multimi se pot face 2 tipuri de 
 operatii, astfel:
 operatia de tipul 1: se dau doua numere naturale x si y, intre 1 si N. Se cere sa 
 reuneasca multimile in care se afla elementul x, respectiv elementul y 
 (se garanteaza ca x si y nu se vor afla in aceeasi multime)
 operatia de tipul 2: se dau doua numere naturale x si y, intre 1 si N. Se cere sa 
 afiseze DA daca cele 2 elemente se afla in aceeasi multime, 
 respectiv NU in caz contrar.
 
 Date de intrare
 Pe prima linie a fisierului de intrare disjoint.in se vor afla 2 numere, N si M, 
 reprezentand numarul de multimi, respectiv numarul de operatii efectuate. Pe 
 urmatoarele M linii se vor afla cate 3 numere, cod, x si y, cod reprezentand tipul 
 operatiei, iar x si y avand semnificatia din enunt.

 Date de ieşire
 In fisierul de iesire disjoint.out se vor afisa mai multe linii, fiecare linie 
 continand DA sau NU, reprezentand raspunsul la interogarea corespunzatoare din 
 fisierul de intrare.

 Restricţii
 1 ≤ N ≤ 100 000
 1 ≤ M ≤ 100 000

 *
 *        Version:  1.0
 *        Created:  12/01/2014 18:57:24
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

#include <cstdio>
#define NMAX 100001

class DisjointDataSet
{
	int parent[NMAX], rang[NMAX];
public:
	DisjointDataSet();
	~DisjointDataSet();
	void makeSet(int);
	void unionTrees(int, int);
	int findRoot(int);
	void link(int x, int y); 
};

DisjointDataSet::DisjointDataSet()
{
}

DisjointDataSet::~DisjointDataSet()
{
}

void DisjointDataSet::makeSet(int x)
{
	parent[x] = x;
	rang[x] = 1;
}

int DisjointDataSet::findRoot(int x)
{
	int i;
	for (i = x; parent[i] != i; i = parent[i])
		;
	// i is the root
	// now compute path compression
	while (parent[x] != x)
	{
		int aux = parent[x];
		parent[x] = i;
		x = aux;
	}
	return i;
}

void DisjointDataSet::link(int x, int y) // here, x and y are roots
{
	if (rang[x] < rang[y])
		parent[x] = y;
	else
		if (rang[x] > rang[y])
			parent[y] = x;
		else 
		{
			parent[x] = y;
			rang[y]++;
		}	
}

void DisjointDataSet::unionTrees(int x, int y)
{
	link(findRoot(x), findRoot(y));
}

int main(int argc, char** argv)
{
	FILE *in, *out;
	int operation, x, y;
	int n, m;

	DisjointDataSet d;

	in  = fopen("disjoint.in", "r");
	out = fopen("disjoint.out", "w");

	fscanf(in, "%d %d", &n, &m);
	
	for (int i = 1; i <= n; i++)
		d.makeSet(i);

	for (int i = 0; i < m; i++)
	{
		fscanf(in, "%d %d %d", &operation, &x, &y);
		
		if (operation == 1)
			d.unionTrees(x, y);
		else
			if (operation == 2)
			{
				if (d.findRoot(x) == d.findRoot(y))
					fprintf(out, "DA\n");
				else 
					fprintf(out, "NU\n");	
			}
	}

	return 0;
}