Se consideră N copii, numerotați de la 1 la N și fiecare face parte dintr-o clasă. Inițial sunt n clase și fiecare copil face parte din propria sa clasă. Se dau M operații de două tipuri:

• 1 x y – acțiune: clasele din care fac parte copiii cu numerele x și y se reunesc. Dacă x și y fac deja parte din aceeași clasă, operația nu se efectuează
• 2 x y – întrebare: copiii cu numerele x și y sunt sau nu în aceeași clasă?

Cerința

Răspundeți la toate întrebările de al doilea tip, în ordinea acestora.

Date de intrare

Programul citește de la tastatură numerele N și M, iar apoi M triplete de numere naturale de forma op x y, unde op poate lua doar valorile 1 și 2, aceste triplete reprezentând câte o operație.

Date de ieșire

Programul va afișa pe ecran, pe câte o linie, răspunsul la fiecare întrebare de tip 2. Dacă la întrebarea 2 x y răspunsul este afirmativ, adică x și y se află în aceeași clasă, atunci veți afișa DA, iar în caz contrar veți afișa NU.

Restricții și precizări

• 1 ≤ N ≤ 500
• 2 ≤ M ≤ 2000
• va exista cel puțin o operație de tip 1 și cel puțin o operație de tip 2.

Exemplu

Intrare

6 6
1 1 4
1 3 6
2 4 6
1 1 3
2 4 6
2 1 6

Ieșire

NU
DA
DA

Explicație

Sunt 6 copii și 6 operații. După primele două operații, elevii 1 și 4 sunt în aceeași clasă și 3 și 6 sunt în aceeași clasă. La întrebarea 2 4 6 răspunsul este evident NU. La a patra operație 1 și 3 sunt trecuți în aceeași clasă, deci va exista o clasă cu 4 copii: {1,3,4,6}, deci la ultimele două întrebări acum răspunsul este DA la ambele.

#include <bits/stdc++.h>

using namespace std;

vector <int>G[101];

struct poz
{
    int val , cul;
}f[2001];
int n , m , x , y , cer , rez[2001] , cnt;

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        f[i].val = i , f[i].cul = i;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> cer >> x >> y;
        if(cer == 1)
        {
            int mini = min(f[x].cul , f[y].cul) , maxi = max(f[x].cul , f[y].cul);
            f[x].cul = mini;
            f[y].cul = mini;
            for(int i = 1 ; i <= n ; i++)
                if(f[i].cul == maxi) f[i].cul = mini;
        }
        else
        {
            if(f[x].cul == f[y].cul) rez[++cnt] = 1;
            else rez[++cnt] = 0;
        }
    }
    for(int i = 1 ; i <= cnt ; i++)
        if(rez[i] == 1) cout << "DA\n";
        else cout << "NU\n";
}