// Bipartit1 pbinfo.ro/probleme/472

// All rights reserved to Claudiu Ursescu ©

#include <bits/stdc++.h>

using namespace std;

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

vector< vector < int > > mat(16, vector< int >(16));
vector< int > color(16, -1);
// 1 = rosu // 0 = albastru

int n, m;
int k;

void read()
{
    fin >> n >> m;
    int x, y;
    for(int i = 1; i <=m; ++i)
    {
        fin >> x >> y;
        mat[x][y] = mat[y][x] = 1;
    }
}

bool isBipartite(int pos, int c)
{
    if(color[pos] != -1 && color[pos] != c)
        return false;

    color[pos] = c;
    bool ok = true;
    for(int i = 1; i <= n; ++i)
    {
        if(mat[i][pos] == 1)
        {
            if(color[i] == -1)
                ok &= isBipartite(i, 1-c);
            if(color[i] != -1 && color[i] != 1-c)
                return false;
        }
        if(!ok)
            return false;
    }
    return true;
}

void print()
{
    int clr = color[1];
    fout << 1 << " ";

    for(int i = 2; i <= n; ++i)
        if(color[i] == clr)
            fout << i << " ";
    fout << endl;
    for(int i = 2; i <= n; ++i)
        if(color[i] != clr)
            fout << i << " ";
}

int main()
{
    read();
    int pos = 1;
    if(isBipartite(pos,1) == true)
        fout << "DA" << endl;
    else
        fout << "NU" << endl;
    print();
    return 0;
}