Se consideră un graf cu N noduri numerotate de la 1 la N și M operații de trei tipuri:

• 1 x y – se adaugă în graf muchia (x, y). Dacă muchia există deja, operația nu se efectuează
• 2 x y – întrebare: nodurile x și y se află sau nu în aceeași componentă conexă?
• 3 – întrebare: care este numărul maxim de noduri dintr-o componentă conexă?

Cerința

Trebuie să răspundeți la toate întrebările de tip 2 și 3.

Date de intrare

Programul citește de la tastatură numerele N și M, iar pe următoarele M linii se află operațiile date fie prin trei valori de forma op x y (pentru operațiile de tip 1 și 2), fie printr-o singură valoare 3 (pentru operațiile de tip 3).

Date de ieșire

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

Restricții și precizări

• 3 ≤ N ≤ 32.000
• 3 ≤ M ≤ 300.000
• va exista cel puțin o operație de fiecare tip.

Exemplu

Intrare

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

Ieșire

NU
DA
4

Explicație

Sunt 6 noduri și 6 operații. După primele două operații, nodurile 1 și 4 sunt în aceeași componentă conexă și 3 și 6 sunt în aceeași componentă conexă. La întrebarea 2 4 6 răspunsul este evident NU. La a patra operație 1 și 3 sunt trecute în aceeași componentă conexă, deci va exista o componentă conexă cu 4 noduri: {1,3,4,6}, deci la întrebarea 2 4 6 răspunsul este DA, iar la ultima operație de tip 3 răspunsul este 4 (componenta conexă maximală are patru noduri).

#include <bits/stdc++.h>

using namespace std;

int T[35001] , n , cer , m , t , C[35001] , maxi;

void leaga(int a , int b)
{
    if(T[a] > T[b])
    {
        T[a] = T[b];
        C[b] = C[a] + C[b];
        if(C[b] > maxi) maxi = C[b];
    }
    else
    {
        T[b] = T[a];
        C[a] = C[b] + C[a];
        if(C[a] > maxi) maxi = C[a];
    }
}

int radacina(int a)
{
    if(a == T[a]) return a;
    else return T[a] = radacina(T[a]);
}
int main()
{
    cin >> n >> m;
    int x , y , c;
    for(int i = 1 ; i <= 33000 ; i++)
        T[i] = i , C[i] = 1;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> cer;
        if(cer == 1)
        {
            cin >> x >> y;
            int r1 , r2;
            r1 = radacina(x);
            r2 = radacina(y);
            if(r1 != r2) leaga(r1 , r2);
        }
        else if(cer == 2)
        {
            cin >> x >> y;
            if(radacina(x) == radacina(y)) cout << "DA" << '\n';
            else cout << "NU" << '\n';
        }
        else
        {
            cout << maxi << '\n';
        }

    }
}