#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <climits>
#include <vector>

using namespace std;

ifstream fin("disjoint.in");
ofstream fout("disjoint.out");

int N, M;
vector <int> predecessor, height;

int findPrecessor(int node)
{
    if(predecessor[node] == 0)
        return node;
    predecessor[node] = findPrecessor(predecessor[node]);
    return predecessor[node];
}

void makeUnion(int x, int y)
{
    int predX = findPrecessor(x);
    int predY = findPrecessor(y);
    if(predX == predY)
        return;
    if(height[predX] >= height[predY])
        predecessor[predY] = predX;
    else
        predecessor[predX] = predY;

}

int main()
{
    fin>>N>>M;
    predecessor.resize(N+1, 0);
    height.resize(N+1, 0);
    for(int i = 0; i < M; i++)
    {
        int operation, x, y;
        fin>>operation>>x>>y;
        if(operation == 1)
            makeUnion(x, y);
        else
        {
            if(findPrecessor(x) != findPrecessor(y))
                fout<<"NU\n";
            else
                fout<<"DA\n";
        }
    }
    for(int i = 1; i <= N; i++)
        cout<<predecessor[i]<<' ';
    cout<<'\n';
    for(int i = 1; i <= N; i++)
        cout<<height[i]<<' ';
    cout<<'\n';
    return 0;
}