#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100100;

vector<int> edges[MAXN];
bool bio[MAXN];
int mat[300][300];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	freopen("puzzle.in", "r", stdin);
	freopen("puzzle.out", "w", stdout);
	
	long long k, p;
	int i, j;
	int a, b;
	int n, m;
	
	cin>>k>>p;
	
	n = (2 * k - p - sqrt(-4 * k + 4 * k * k - 4 * k * p + p * p)) / 2;
	m = (2 * k - p + sqrt(-4 * k + 4 * k * k - 4 * k * p + p * p)) / 2;
	
	cout<<n<<' '<<m<<'\n';
	
	for (i = 0; i < p; ++i)
	{
		cin>>a>>b;
		--a, --b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	if (n == 1)
	{
		cout<<a + 1<<' ';
		int prv = a, tmp;
		a = edges[a][0];
		while (edges[a].size() == 2)
		{
			cout<<a + 1<<' ';
			tmp = (edges[a][0] == prv ? edges[a][1] : edges[a][0]);
			prv = a;
			a = tmp;
		}
		cout<<a + 1<<'\n';
	}
	for (i = 0; i < k; ++i) if (edges[i].size() == 2)
	{
		a = i;
		break;
	}
	
	mat[0][0] = a + 1;
	bio[a] = true;
	
	if (n == 2)
	{
		b = (edges[edges[a][0]].size() == 2 ? edges[a][0] : edges[a][1]);
		int x, y, prva, prvb;
		j = 0;
		
		while (a != -1)
		{
			mat[0][j] = a + 1;
			mat[1][j] = b + 1;
			++j;
			
			x = -1;
			for (int u: edges[a]) if (u != prva && u != b)
				x = u;
			y = -1;
			for (int u: edges[b]) if (u != prvb && u != a)
				y = u;
			
			prva = a;
			prvb = b;
			
			a = x;
			b = y;
		}
		
		for (i = 0; i < n; ++i)
		{
			for (j = 0; j < m; ++j)
				cout<<mat[i][j]<<' ';
			cout<<'\n';
		}
		return 0;
	}
	
	int cnt = 1;
	{
		int prv = a, tmp;
		a = edges[a][0];
		while (edges[a].size() == 3)
		{
			++cnt;
			for (int x: edges[a]) if (x != prv && edges[x].size() < 4)
				tmp = x;
			prv = a;
			a = tmp;
		}
		++cnt;
	}
	a = mat[0][0] - 1;
	if (cnt != m)
		swap(edges[a][0], edges[a][1]);
	
	vector<pair<int, int>> cur, nxt;
	{
		i = 0; j = 0;
		int prv = a, tmp;
		a = edges[a][0];
		while (edges[a].size() == 3)
		{
			mat[i][++j] = a + 1;
			bio[a] = true;
			cur.push_back({i, j});
			for (int x: edges[a]) if (x != prv && edges[x].size() < 4)
				tmp = x;
			prv = a;
			a = tmp;
		}
		mat[i][++j] = a + 1;
		bio[a] = true;
		tmp = (edges[a][0] == prv ? edges[a][1] : edges[a][0]);
		prv = a;
		a = tmp;
		while (edges[a].size() == 3)
		{
			mat[++i][j] = a + 1;
			bio[a] = true;
			cur.push_back({i, j});
			for (int x: edges[a]) if (x != prv && edges[x].size() < 4)
				tmp = x;
			prv = a;
			a = tmp;
		}
		mat[++i][j] = a + 1;
		bio[a] = true;
		tmp = (edges[a][0] == prv ? edges[a][1] : edges[a][0]);
		prv = a;
		a = tmp;
		while (edges[a].size() == 3)
		{
			mat[i][--j] = a + 1;
			bio[a] = true;
			cur.push_back({i, j});
			for (int x: edges[a]) if (x != prv && edges[x].size() < 4)
				tmp = x;
			prv = a;
			a = tmp;
		}
		mat[i][--j] = a + 1;
		bio[a] = true;
		tmp = (edges[a][0] == prv ? edges[a][1] : edges[a][0]);
		prv = a;
		a = tmp;
		while (edges[a].size() == 3)
		{
			mat[--i][j] = a + 1;
			bio[a] = true;
			cur.push_back({i, j});
			for (int x: edges[a]) if (x != prv && edges[x].size() < 4)
				tmp = x;
			prv = a;
			a = tmp;
		}
	}
	
//	for (i = 0; i < n; ++i)
//	{
//		for (j = 0; j < m; ++j)
//			cout<<mat[i][j]<<' ';
//		cout<<'\n';
//	}
	
	while (cur.size())
	{
		nxt.clear();
		for (const auto& pos: cur)
		{
			tie(i, j) = pos;
			a = mat[i][j] - 1;
			int tmp = -1;
			for (int x: edges[a]) if (!bio[x])
				tmp = x;
			if (tmp == -1)
				continue;
			for (int ii = -1; ii <= 1; ++ii) for (int jj = -1; jj <= 1; ++jj) if ((!ii ^ !jj) && i + ii >= 0 && i + ii < n && j + jj >= 0 && j + jj < m && !mat[i + ii][j + jj])
			{
				i += ii;
				j += jj;
				goto out;
			}
			out:
//			cout<<a<<' '<<tmp<<' '<<i<<' '<<j<<'\n';
			mat[i][j] = tmp + 1;
			bio[tmp] = true;
			nxt.push_back({i, j});
		}
		swap(cur, nxt);
	}
	
	for (i = 0; i < n; ++i)
	{
		for (j = 0; j < m; ++j)
			cout<<mat[i][j]<<' ';
		cout<<'\n';
	}
}