#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <utility>
 
using namespace std;

class Graf
{
private:
    static constexpr int NMAX = 100009;
    const int N, M;
    vector<int> Adiacenta[NMAX];  // liste de adiacenta
 
public:
    Graf(int, int);
    void AdMuchie(int, int);

    static constexpr int getNMAX() { return Graf::NMAX; }

public:
    void Bfs(int, int*);
    int Dfs();
    void Biconex(vector<vector<int>>&);
    void CompTareConexe(vector<int>*, vector<vector<int>>&, int&);
    void MuchieCritica(vector<vector<int>>&);
    void ProbGraf_NoduriComune(int, int, vector<int>&);
    void SortTopo(int*);

    // Tema 2 aici

    static bool HavelHakimi(int*, int);
    static void Disjoint(int, vector<vector<int>>&, vector<string>&);

private:
    void Dfs_fHelper(int, bool*);
    void Biconex_fHelper(int, int, pair<int, int>*, int&, int*, int*, vector<vector<int>>&);
    void CompTareConexe_Dfs(int, bool*, int*, int&);
    void CompTareConexe_t_Dfs(int, bool*, vector<int>*, vector<vector<int>>&, int);
    void MuchieCritica_fHelper(int, int, int*, int*, vector<vector<int>>&);
    void NoduriComune_BfsInainte(int, int, int*);
    void NoduriComune_BfsInapoi(int, int, int*, int*, vector<int>&);
};
 
Graf::Graf(int n, int m)
    : N(n), M(m)
{
}
 
void Graf::AdMuchie(int ini, int fin)
{
    Adiacenta[ini].push_back(fin);
}

void Graf::Bfs(int S, int* nrArce)
{
    int coada[NMAX], st = 0, dr = 0;
 
    for (int i = 1; i <= N; ++i)
        nrArce[i] = -1;
    nrArce[S] = 0;
    coada[st] = S;
    while (st <= dr)
    {
        int curent = coada[st++];
        for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
            if(nrArce[*it] == -1)
            {
                coada[++dr] = *it;
                nrArce[*it] = nrArce[curent] + 1;
            }
    }
}

int Graf::Dfs()
{
    bool vizitat[NMAX];
    int nrComp = 0;

    memset(vizitat, 0, NMAX * sizeof(bool));
    for (int i = 1; i <= N; ++i)
        if (!vizitat[i])
        {
            ++nrComp;
            Dfs_fHelper(i, vizitat);
        }

    return nrComp;
}

void Graf::Dfs_fHelper(int curent, bool* vizitat)
{
    vizitat[curent] = true;
    for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
        if (!vizitat[*it])
            Dfs_fHelper(*it, vizitat);
}

void Graf::Biconex(vector<vector<int>>& compBic)
{
    pair<int, int> Stiva[NMAX * 2];
    int stVf = 0;
    int nivelInArbDFS[NMAX];  // folosit si ca vizitat[]
    int nivelMinVecini[NMAX];

    nivelInArbDFS[0] = 0;
    Biconex_fHelper(1, 0, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);
}

void Graf::Biconex_fHelper(int nod, int parinte, pair<int, int>* Stiva, int& stVf, int* nivelInArbDFS, int* nivelMinVecini, vector<vector<int>>& compBic)
{
    nivelInArbDFS[nod] = nivelInArbDFS[parinte] + 1;
    nivelMinVecini[nod] = NMAX;
    for (int& vecin : Adiacenta[nod])
    {
        if (nivelInArbDFS[vecin])  // daca e vizitat
        {
            if (nivelMinVecini[nod] > nivelInArbDFS[vecin] && vecin != parinte)
                nivelMinVecini[nod] = nivelInArbDFS[vecin];
        }
        else
        {
            Stiva[++stVf] = {nod, vecin};
            Biconex_fHelper(vecin, nod, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);

            if (nivelMinVecini[nod] > nivelMinVecini[vecin])
                nivelMinVecini[nod] = nivelMinVecini[vecin];
            
            if (nivelMinVecini[vecin] >= nivelInArbDFS[nod])
            {
                compBic.push_back({});
                while (Stiva[stVf].first != nod)
                    compBic.back().push_back(Stiva[stVf--].second);
                compBic.back().push_back(Stiva[stVf].second);  // muchia din 'nod', intreaga
                compBic.back().push_back(Stiva[stVf].first);   //
                --stVf;
            }
        }
    }
}

void Graf::CompTareConexe(vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int& nrComp)
{
    int stivaTopo[NMAX], stVf = 0;    // stivaTopo - stiva de noduri in care nodurile sunt inserate in ordinea topologica inversata
    bool vizitat[NMAX];

    memset(vizitat, 0, (N + 1) * sizeof(bool));
    for (int nod = 1; nod <= N; ++nod)
        if (!vizitat[nod])
            CompTareConexe_Dfs(nod, vizitat, stivaTopo, stVf);

    compTC.resize(N);
    nrComp = 0;
    memset(vizitat, 0, (N + 1) * sizeof(bool));
    while (stVf)
    {
        if (!vizitat[stivaTopo[stVf]])
            CompTareConexe_t_Dfs(stivaTopo[stVf], vizitat, t_Adiacenta, compTC, nrComp++);
        --stVf;
    }
}

void Graf::CompTareConexe_Dfs(int nod, bool* vizitat, int* stivaTopo, int& stVf)
{
    vizitat[nod] = true;
    for (auto& vecin : Adiacenta[nod])
        if (!vizitat[vecin])
            CompTareConexe_Dfs(vecin, vizitat, stivaTopo, stVf);
    stivaTopo[++stVf] = nod; 
}

void Graf::CompTareConexe_t_Dfs(int nod, bool* vizitat, vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int nrComp)
{
    vizitat[nod] = true;
    for (auto& vecin : t_Adiacenta[nod])
        if (!vizitat[vecin])
            CompTareConexe_t_Dfs(vecin, vizitat, t_Adiacenta, compTC, nrComp);
    compTC[nrComp].push_back(nod);
}

void Graf::MuchieCritica(vector<vector<int>>& mCritice)
{
    int nivelInArbDFS[NMAX];  // folosit si ca vizitat[]
    int nivelMin[NMAX];

    memset(nivelInArbDFS, 0, (N + 1) * sizeof(int));
    MuchieCritica_fHelper(0, 0, nivelInArbDFS, nivelMin, mCritice);
}

void Graf::MuchieCritica_fHelper(int nod, int parinte, int* nivelInArbDFS, int* nivelMin, vector<vector<int>>& mCritice)
{
    nivelInArbDFS[nod] = nivelMin[nod] = nivelInArbDFS[parinte] + 1;
    for (int& vecin : Adiacenta[nod])
    {
        if (nivelInArbDFS[vecin])
        {
            if (nivelMin[nod] > nivelInArbDFS[vecin] && vecin != parinte)
                nivelMin[nod] = nivelInArbDFS[vecin];
        }
        else
        {
            MuchieCritica_fHelper(vecin, nod, nivelInArbDFS, nivelMin, mCritice);

            if (nivelMin[nod] > nivelMin[vecin])
                nivelMin[nod] = nivelMin[vecin];

            // muchie critica
            if (nivelMin[vecin] > nivelInArbDFS[nod])  // nivelMin[vecin] == nivelInArbDFS[vecin]
                mCritice.push_back({nod, vecin});
        }
    }
}

void Graf::ProbGraf_NoduriComune(int X, int Y, vector<int>& noduri)
{
    int lungime[NMAX];  // folosit si ca vizitat[] in BfsInainte => lungimea se calculeaza incepand de la 1
    int nrVizite[NMAX];  // folosit in BfsInapoi pt a identifica unificarea ramurilor (si pentru vizitat[])

    noduri.push_back(X);
    // noduri.push_back(Y);  -- nu e nevoie, e mereu primul adaugat in BfsInapoi
    NoduriComune_BfsInainte(X, Y, lungime);
    NoduriComune_BfsInapoi(X, Y, lungime, nrVizite, noduri);

    sort(noduri.begin(), noduri.end());
}

void Graf::NoduriComune_BfsInainte(int X, int Y, int* lungime)
{
    int coada[NMAX], st = 0, dr = -1;
    bool COADA_STOP_INTRARI = false;

    coada[++dr] = X;
    lungime[X] = 1;
    while (st <= dr)
    {
        int nodCurent = coada[st++];
        for (int& vecin : Adiacenta[nodCurent])
            if (!lungime[vecin])
            {
                lungime[vecin] = lungime[nodCurent] + 1;
                if (vecin == Y)
                    COADA_STOP_INTRARI = true;
                if (!COADA_STOP_INTRARI)
                    coada[++dr] = vecin;
            }
    }
}

void Graf::NoduriComune_BfsInapoi(int X, int Y, int* lungime, int* nrVizite, vector<int>& noduri)
{
    int nrRamuri = 1;   // total ramuri existente la pasul curent

    int coada[NMAX], st = 0, dr = -1;
    coada[++dr] = Y;
    while (st <= dr)
    {
        int nodCurent = coada[st++];
        int ramuriDinCurent = 0;      // cate ramuri pornesc din nodul curent, cel putin una din moment ce avem drum mai departe

        if (nrRamuri == 1)
            noduri.push_back(nodCurent);

        for (int& vecin : Adiacenta[nodCurent])
        {
            if (lungime[vecin] == lungime[nodCurent] - 1)
            {
                ++ramuriDinCurent;
                ++nrVizite[vecin];
                if (nrVizite[vecin] > 1)
                    --nrRamuri;
                if (vecin == X)
                    break;
                if (nrVizite[vecin] == 1)
                    coada[++dr] = vecin;
            }
        }

        nrRamuri += (ramuriDinCurent - 1); 
    }                                 
}

void Graf::SortTopo(int* noduri)
{
    bool vizitat[NMAX];
    int dr = 0;
    
    memset(vizitat, 0, (N + 1) * sizeof(bool));
    for (int nod = 1; nod <= N; ++nod)
        if (!vizitat[nod])
            CompTareConexe_Dfs(nod, vizitat, noduri, dr);
    reverse(noduri + 1, noduri + 1 + N);
}

bool Graf::HavelHakimi(int* S, int N)
{
    auto descrescator = [](int a, int b) { return a > b; };
    sort(S, S + N, descrescator);

    if (S[0] >= N)
        return false;
    
    int grMax, pozPrimElem = 0;
    while (S[pozPrimElem] > 0)
    {   
        grMax = S[pozPrimElem++];
        for (int i = pozPrimElem; i < pozPrimElem + grMax; ++i)
            --S[i];

        sort(S + pozPrimElem, S + N, descrescator);
        if (S[N - 1] < 0)
            return false;
    }
    return true;
}

void Graf::Disjoint(int N, vector<vector<int>>& Operatii, vector<string>& Raspuns)
{
    int tata[NMAX], rang[NMAX];  // rangurile arborilor se retin in radacini
    memset(tata, 0, N * sizeof(int));
    memset(rang, 0, N * sizeof(int));  // va fi inaltime - 1

    for (auto& op : Operatii)
    {
        int x = op[1];
        int y = op[2];

        if (op[0] == 1)
        {
            while (tata[x])
                x = tata[x];
            while (tata[y])
                y = tata[y];

            if (rang[x] > rang[y])  // fiindca rang[x] e strict mai mare decat rang[y], 
                tata[y] = x;        // adaugarea arb. Y ca subarb. al lui X nu va putea creste rang[x]
            else // rang[x] <= rang[y]
            {
                tata[x] = y;
                if (rang[y] == rang[x])   // daca rangurile sunt egale, prin legarea rad., rangul celui de care s-a legat va creste cu 1
                    ++rang[y];
            }
        }
        else
        {
            int radX = x;
            while (tata[radX])
                radX = tata[radX];
            
            int radY = y;
            while (tata[radY])
                radY = tata[radY];

            if (radX != radY)
                Raspuns.emplace_back("NU");
            else
                Raspuns.emplace_back("DA");

            // Compresia drumurilor

            int nod = x;
            while (tata[nod])
            {
                int old = tata[nod];
                tata[nod] = radX;
                nod = tata[old];
            }

            nod = y;
            while (tata[nod])
            {
                int old = tata[nod];
                tata[nod] = radY;
                nod = tata[old];
            }
        }
    }
}

int main()
{   
    ifstream f("disjoint.in");
    ofstream g("disjoint.out");
    int N, M;
    vector<vector<int>> Op;

    f >> N >> M;
    Op.reserve(M);
    for (int cod, x, y, i = 0; i < M; ++i)
    {
        f >> cod >> x >> y;
        Op.push_back({cod, x, y});
    }

    vector<string> Raspuns;
    Graf::Disjoint(N, Op, Raspuns);

    for (string& R : Raspuns)
        g << R << '\n';
    
    return 0;
}