#include <iostream>
#include <cstdio>
using namespace std;

const long MaxN = 1001;

long n, m;

long susedCnt[MaxN];
long sused[MaxN][MaxN]; // broj cvorova je mali pa mozemo i ovako da pamtimo listu suseda

bool grupa[MaxN];	 // da li pripada prvoj grupi?
long grupaCnt[MaxN]; // koliko cvor gadja unutar svoje grupe
bool dobar[MaxN]; // da li je cvor u listi dobrih ili losih cvorova

// lista suseda zadovoljenih i nezadovoljenih cvorova
long next[MaxN];
long prev[MaxN];

// pocetak liste
int goodStart, badStart;


char fileIn[] = "mika.in";
char fileOut[] = "mika.out";


void ubaci(int &list, int k)
{
	if (list == -1)
	{
		// prazna lista
		list = k;
		prev[k] = -1;
		next[k] = -1;
	}
	else
	{
		// na pocetak
		prev[list] = k;
		next[k] = list;
		prev[k] = -1;
		list = k;
	}
}

void izbaci(int &list, int k)
{
	if (list == k)
	{
		list = next[list];
		if (list != -1)
			prev[list] = -1;
	}
	else
	{
		next[prev[k]] = next[k];
		if (next[k] != -1)
			prev[next[k]] = prev[k];
	}
}


// dodaje nov cvor u odgovarajucu listu
void novCvor(int k)
{
	if (grupaCnt[k] > susedCnt[k] / 2)
	{
		// los cvor
		dobar[k] = false;
		ubaci(badStart, k);
	}
	else
	{
		// dobar cvor
		dobar[k] = true;
		ubaci(goodStart, k);
	}
}


void transfer()
{
	int v = badStart;

	// posle prebacivanja, cvor postaje dobar
	dobar[v] = true;
	izbaci(badStart, v);
	ubaci(goodStart, v);


	for (int i = 0; i < susedCnt[v]; i++)
	{
		int w = sused[v][i];
		if (grupa[w] == grupa[v])
		{
			// bili ista grupa, vise nisu
			grupaCnt[w]--;
			grupaCnt[v]--;

			// mozda je postao dobar
			if (!dobar[w] && (grupaCnt[w] <= susedCnt[w] / 2))
			{
				// izbacujemo ga iz liste losih, i guramo u listu dobrih
				dobar[w] = true;
				izbaci(badStart, w);
				ubaci(goodStart, w);
			}
		}
		else
		{
			// postali su ista grupa
			grupaCnt[w]++;
			grupaCnt[v]++;

			// mozda je cvor w postao los
			if (dobar[w] && (grupaCnt[w] > susedCnt[w] / 2))
			{
				// izbacujemo ga iz liste dobrih, i guramo u listu losih
				dobar[w] = false;
				izbaci(goodStart, w);
				ubaci(badStart, w);
			}
		}
	}

	// promeni grupu
	grupa[v] = !grupa[v];
}


int main()
{	
	FILE *f = fopen(fileIn, "r");
	fscanf(f, "%ld %ld", &n ,&m);

	for (int i = 0; i < n; i++)
	{
		grupaCnt[i] = 0;
		susedCnt[i] = 0;

		// inicijalna grupa
		if (i < n/2) grupa[i] = true;
		else grupa[i] = false;
	}

	for (long i = 0; i < m; i++)
	{
		long a, b;
		fscanf(f, "%ld %ld", &a, &b);
		a--; b--;

		sused[a][susedCnt[a]++] = b;
		sused[b][susedCnt[b]++] = a;

		if (grupa[a] == grupa[b])
		{
			grupaCnt[a]++;
			grupaCnt[b]++;
		}
	}
	fclose(f);

	goodStart = -1;
	badStart = -1;
	for (int i = 0; i < n; i++)
		novCvor(i);

	// prebacujemo iz jedne grupe u drugu, dokle god mozemo
	while (badStart != -1)
	{
		transfer();
	}

	int grupa1 = 0, grupa2 = 0;
	for (int i = 0; i < n; i++)
	{
		if (grupa[i])
			grupa1++;
		else
			grupa2++;
	}

	f = fopen(fileOut, "w");
	fprintf(f, "%d %d\n", grupa1, grupa2);

	for (int i = 0; i < n; i++)
		if (grupa[i]) fprintf(f, "%d ", (i+1));
	fprintf(f, "\n");
	for (int i = 0; i < n; i++)
		if (!grupa[i]) fprintf(f, "%d ", (i+1));
	fprintf(f, "\n");
	fclose(f);

	return 0;
}