//#include <vector>
//#include <fstream>
//using namespace std;
//
//ifstream fin("disjoint.in");
//ofstream fout("disjoint.out");
//
//class DisjointSets
//{
//private:
//    int n; //numarul de noduri
//    vector<int> rep; //vectorul de reprezentanti(conform cursului)
//    vector<int> h; //vector ce va retine inaltimile arborilor
//
//public:
//    DisjointSets(int n);//constructor parametrizat care face si initializarea vectorului de preprezentanti
//    int Reprezentant(int x);//metoda ce returneaza reprezentantul unui nod x dat
//    void Reuniune(int x, int y);//metoda ce reuneste arborii care contin nodurile x si y
//
//};
//
//DisjointSets::DisjointSets(int n)
//{
//    this->n = n;
//    //initializam vectorul de reprezentanti si pe cel de inaltimi
//    rep.resize(n+1);
//    h.resize(n+1);
//    for(int i=1; i<=n; ++i)
//        rep[i] = i;
//};
//
//int DisjointSets::Reprezentant(int x)
//{
//    //daca x este chiar radacina(el este reprezentantul sau)
//    if(x == rep[x])
//        return x;
//    else //altfel reprezentantul lui x va fi reprezentantul tatalui sau(apel recursiv)
//    {
//        //efectuam compresia asupra arborelui
//        int r = Reprezentant(rep[x]); //aflu reprezentantul parintelui lui x
//        rep[x] = r;
//        return r;
//    }
//}
//
//void DisjointSets::Reuniune(int x, int y)
//{
//    //aflam rep lui x si y
//    int rx = Reprezentant(x);
//    int ry = Reprezentant(y);
//
//    //daca x si y au acelasi reprezentant, atunci acestia sunt deja in aceeasi multime(nu am ce sa reunesc)
//    if(rx == ry)
//        return;
//
//    //subordonez reprezentantul din arborele cu inaltime mai mica reprezentantului din arborele cu inaltime mai mare
//    if(h[rx] < h[ry])
//        rep[rx] = ry;
//    else if(h[rx] > h[ry])
//        rep[ry] = rx;
//    else //au inaltimi egale caz in care inaltimea creste cu 1 dupa subordonare
//    {
//        rep[rx] = ry;
//        h[ry]++;
//    }
//
//}
//
//int main()
//{
//
//    int n,m,x,y,op;
//    //citim datele
//    fin >> n >> m;
//
//    //definesc o instanta a clasei DisjointSets
//    DisjointSets dj(n);
//
//    for(int i=0; i<m; ++i)
//    {
//        fin >> op >> x >> y;
//        if(op == 1)
//            dj.Reuniune(x,y);
//        else
//        {
//            //aflam reprezentantii lui x si y pt a vedea din ce multimi fac parte
//            int rx = dj.Reprezentant(x);
//            int ry = dj.Reprezentant(y);
//
//            if(rx == ry) //daca x si y fac parte din aceeasi multime
//                fout << "DA\n";
//            else
//                fout << "NU\n";
//        }
//    }
//
//    return 0;
//}