/* GCC */

#define maxn 2000

#include <stdio.h>
#include <vector>

using namespace std;

int n, m, i, a, b, owners[maxn], owner;
vector<int> g[maxn];   // Граф: g[i] міститиме динамічний масив номерів вершин, суміжних із вершиною i (індексація з нуля)
bool first;

// Рекурсивна функція для пошуку в глибину
// v — номер вершини (від 0 до n-1)
// owner — власник, якого потрібно присвоїти вершині (1 або 2)
// Повертає true, якщо вершини вдалося розподілити, та false, якщо ні
bool dfs(int v, int owner)
{
     owners[v] = owner;    // Присвоєюємо вершині кабінет
     for (int i = 0; i < g[v].size(); i++)      // Для всіх суміжних із нею вершин
     {
         int w = g[v][i];     // Номер суміжної вершини
         if (owners[w] == 0)   // Якщо в цю суміжну вершину пошук у глибину ще не заходив
         {
            if (! dfs(w, 3 - owner))   // Заходимо у вершину з протилежним номером власника; якщо десь на глибших етапах пошуку власників не вдалося розподілити, то власників не можна розподілити в принципі — повертаємо false
               return false;
         }
         else if (owners[w] == owner)   // Якщо в суміжну вершину ми вже заходили і присвоїли їй того ж власника, що й даній вершині, розподілити вершини неможливо — повертаємо false
              return false;    
     }
     return true;    // Ми пройшли по всіх суміжних вершинах і змогли присвоїти їм власників — повертаємо true
}

int main()
{
    freopen("wrappers.in", "r", stdin);
    freopen("wrappers.out", "w", stdout);
    
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
        g[a - 1].push_back(b - 1);   // Додаємо ребра до графа, враховуючи, що індексація у задачі з одиниці, а у програмі — з нуля
        g[b - 1].push_back(a - 1);
    }
    for (i = 0; i < n; i++)  // Кожній із вершин спершу присвоюємо стан «іще не відомо, якого власника їй слід присвоїти»
        owners[i] = 0;
    
    if (dfs(0, 1)) // Якщо вершини компоненти зв’язності, до якої належить вершина 0, можна розподілити
    {
        for (i = 0; i < n; i++)
            if (owners[i] == 0) // Якщо хоча б одній вершині ще не присвоєно власника, це означає, що граф містить принаймні дві компоненти зв’язності, тому якщо розподіл усіх вершин графа існує, то він не єдиний, тому (згідно з умовою задачі) розподілу немає взагалі: виводимо нулі й виходимо
            {
               printf("0\n0\n");
               return 0;
            }
        // Якщо ж усім вершинам присвоєно власників, ми знайшли потрібний розподіл — виводимо його
        for (owner = 1; owner <= 2; owner++) // Для кожного власника
        {
            first = true;   // Поки що ми не вивели номера жодної вершини, що належить даному власнику
            for (i = 0; i < n; i++) // Для кожної вершини
                if (owners[i] == owner)  // Якщо вершина присвоєна даному власнику
                {
                   if (! first)   // Якщо це не перша вершина для даного власника, виводимо перед її номером пробіл
                      printf(" ");      
                   printf("%d", i + 1); // Виводимо номер вершини, враховуючи, що у програмі індексація з нуля, а в задачі — з одиниці
                   first = false;       // Хоча б одну вершину, що належить даному власнику, ми щойно вивели
                }
            printf("\n");  // Після номерів вершин кожного власника має бути ознака кінця рядка
        }
    }
    else        // Якщо вершини компоненти зв’язності, до якої належить вершина 0, неможливо розподілити, виводимо нулі
        printf("0\n0\n");
 
    return 0;   
}
