#include<iostream>
#include<set>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int size = 10;//game size
const int times = 9;
const int partyN = 18;
//time , size
int partyBoard[times][size][2] = { 0 };//0 is empty
bool usedParty[times][partyN+1];//1~18, party in this time
bool playedGame[partyN+1][size];//has this party played this game?
set< pair<int, int>  > vs;//party vs party

void init()
{
	
	for (int i = 0; i < times; i++)
	{
		for (int j = 0; j < size; j++)
		{
			partyBoard[i][j][0] = 0;
			partyBoard[i][j][1] = 0;
		}
		for (int j = 0; j < partyN+1; j++)
		{
			usedParty[i][j] = false;
			playedGame[j][i] = false;
		}
	}
}


void show()
{

	for (int i = 0; i < times; i++)
	{
		for (int j = 0; j < size; j++)
		{
			if (i != 1)
				printf(" ");

			printf("(%2d,%2d) ", partyBoard[i][j][0], partyBoard[i][j][1]);

		}
		printf("\n");
	}
}

//x is game
//y is time
bool backTrack(int x, int y, int r)
{	
//	show();
	if (x == size)
	{
		if (r==0)
			return backTrack(0, y + 1, partyN);
		else
			return false;
	}
	if (y == times)
	{
		return true;
	}


	for (int i = 1; i < partyN + 1; i++)
	for (int j = i + 1; j < partyN + 1; j++)
	{
		if (usedParty[y][i] == false && usedParty[y][j] == false)//time, party
		if (playedGame[i][x] == false && playedGame[j][x] == false)//party, game
		if (vs.count(make_pair(i,j))==0)
		{
	

			//push
			partyBoard[y][x][0] = i;
			partyBoard[y][x][1] = j;
			usedParty[y][i] = true;
			usedParty[y][j] = true;
			playedGame[i][x] = true;
			playedGame[j][x] = true;
			vs.insert(make_pair(i, j));

			if (backTrack(x+1,y,r-2))
			{
				return true;
			}

			//pop
			partyBoard[y][x][0] = 0;
			partyBoard[y][x][1] = 0;
			usedParty[y][i] = false;
			usedParty[y][j] = false;
			playedGame[i][x] = false;
			playedGame[j][x] = false;
			vs.erase(make_pair(i, j));
		}
	}

	//skip game
	if (size-1-x>=r/2)
	if (backTrack(x+1,y,r))
		return true;

	return false;
}



int main(int argc, char* argv[])
{

	cout << backTrack(0, 0, 18) << endl;

	show();
	return 0;
}