//* Problem  : 1063 - Domino Puzzle
//* Contest  : acm.timus.ru
//* Type     : Solution
//* Date     : 2007.11.10
//* Author   : alt
//* Language : C++
//* Compiler : Microsoft Visual C++ 6.0

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

const int edges[][2] = {
	{1, 2},
	{1, 3},
	{1, 4},
	{1, 5},
	{1, 6},
	{2, 3},
	{2, 4},
	{2, 5},
	{2, 6},
	{3, 4},
	{3, 5},
	{3, 6},
	{4, 5},
	{4, 6},
	{5, 6},
	{1, 2},
	{1, 3},
	{1, 4},
	{1, 5},
	{1, 6},
	{2, 3},
	{2, 4},
	{2, 5},
	{2, 6},
	{3, 4},
	{3, 5},
	{3, 6},
	{4, 5},
	{4, 6},
	{5, 6}
};

const char *fin = "tests\\domino.25";

const int total = sizeof(edges) / sizeof(edges[0]);

int n, a[100][2];
int r[100][2], resn, resk;
int bits[100];

void solve();
void result();

int valid[7];
int root[7];
int adjc[7];

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d%d", &a[i][0] , &a[i][1]);
	solve();
	result();
	return 0;
}

void set_first(int cnt, int k)
{
	memset(bits, 0, sizeof(bits));
	for (int i = k - 1; i >= k - cnt; i--)
		bits[i] = 1;
}

int get_next(int cnt, int k)
{
	int i;
	for (i = 0; i < cnt; i++)
		if (!bits[i]) break;
	if (i == cnt) return 0;
	int left = k - 1, pos = k - 1;
	while (1)
	{
		while (!bits[pos]) pos--;
		bits[pos] = 0;
		if (!bits[pos-1]) {bits[pos-1] = 1; return 1;}
		bits[left--] = 1;
		pos--;
	}
	return 1;
}


int croot[7], cadjc[7];
int tmpres[10][2];



int connected()
{
	for (int i = 1; i < 6; i++)
		if (valid[i])
			for (int j = i + 1; j <= 6; j++)
				if (valid[j] && croot[i] != croot[j])
					return 0;
	return 1;
}

int ok()
{
	int r = (cadjc[1]%2) + (cadjc[2]%2) + (cadjc[3]%2) + (cadjc[4]%2) + (cadjc[5]%2) + (cadjc[6]%2);
	return (r <= 2);
}

void connect(int v1, int v2)
{
	int k1 = croot[v1], k2 = croot[v2];
	if (k1 == k2) return;
	for (int i = 1; i <= 6; i++)
		if (croot[i] == k1)
			croot[i] = k2;
}

void try_this(int count)
{
	int i, j;
	for (i = 1; i <= 6; i++)
	{
		croot[i] = root[i];
		cadjc[i] = adjc[i];
	}
	int sum = 0, t = 0;
	for (i = 0; i < total; i++)
		if (bits[i])
		{
			int v1 = edges[i][0];
			int v2 = edges[i][1];
			cadjc[v1]++;
			cadjc[v2]++;
			sum += v1 + v2;
			connect(v1, v2);
			tmpres[t][0] = edges[i][0];
			tmpres[t++][1] = edges[i][1];
		}
	if (sum < resn && connected() && ok())
	{
		resn = sum;
		resk = count;
		memcpy(r, tmpres, 8 * resk);
	}
}

void solve()
{
	int i, j, t;
	for (i = 1; i <= 6; i++)
		root[i] = i;
	for (i = 0; i < n; i++)
	{
		valid[a[i][0]] = valid[a[i][1]] = 1;
		adjc[a[i][0]]++;
		adjc[a[i][1]]++;
		int t1 = root[a[i][0]];
		int t2 = root[a[i][1]];
		for (j = 1; j <= 6; j++)
			if (root[j] == t1)
				root[j] = t2;
	}
	resn = 1000000;
	resk = 0;
	for (int count = 0; count <= 5; count++)
	{
		set_first(count, total);
		try_this(count);
		while (get_next(count, total))
			try_this(count);
	}
}

void result()
{
	printf("%d\n%d\n", resn, resk);
	for (int i = 0; i < resk; i++)
		printf("%d %d\n", r[i][0], r[i][1]);
}

