#include <iostream>
#include <fstream>

using namespace std;

int n, ok=1;
ifstream f("bfs.in");
ofstream g("bfs.out")
void citire(int m[100][100]) //citire
{
    f>>n;
    int x,y;
    while(f>>x>>y)
        m[x][y] = m[y][x] = 1;
}

void DFS(int x, int c,int m[100][100], int culoare[101])
{
    culoare[x] = c;                // parcurgem cu metoda DFS si incercam sa coloram graful intr-o 2-colorare. Daca se poate inseamna ca putem imparti persoanele corect,
    for(int i = 1 ;i <= n;i ++)    // iar altfel(2 culori una langa alta) inseamna ca exista 2 "dusmani" unul langa celalalt, ceea ce e interzis din cerinta
        if(m[x][i]==1)
        {
            if(culoare[i]==0)
                DFS(i,-c,m,culoare);
            else
            if(culoare[x] == culoare[i]) // verificam conditia sa nu fie 2 culori una langa alta
                ok=0;
        }
}

int main()
{
    int m[100][100], culoare[101];
    citire(m);
    int verif=1; //presupunem ca graful este bun
    for(int i=1;i<=n;i++)
    {
        verif=1;
        if(culoare[i] == 0) //daca nodul curent nu este colorat
        {
            ok=1;
            DFS(i,1,m,culoare); //parcugem vecinii nodului curent
            verif=(verif && ok);
        }
    }
    if(verif) //daca a trecut de toate conditiile
    {
        g<<"true"<<endl;
        for(int i=1;i<=n;i++)
            if(culoare[i]==1)
                g<<i<<" ";
        cout<<endl;
        for(int i=1;i<=n;i++)
            if(culoare[i]==-1)
                g<<i<<" ";
    }
    else
        g<<"false"<<endl;
    return 0;
}
//complexitatea algoritmului:
//preprocesare: O(n)
//procesare; O(n+m)