//从叶子结点向上构造二叉树，只是加了一点剪枝 但…………求大佬找一下剪枝的错误
//剪枝的思路是对于每个产生的子树标号并判重，即由（a,b）构成的节点只构造一次
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
void init();
void bfs(int);
void Pr(int);//打印二叉树 
struct toTr//节点 
{
	int value,no,soLe,soRi;//用于判重的值,二叉树节点数组中的位置，左子树在数组中的位置,右子树 
	toTr operator = (toTr &b)
	{
		memcpy(this,&b,sizeof(toTr));
		return *this;
	}
};

const int N = 10000;
typedef pair<int,int> pa; 
map<pair<int,int>,bool>un;
toTr a[N];
int b[N],n,cnt,ct;//b[i]标记已合成的节点 cnt判重 ct当前二叉树含有节点数量 
int main()
{
	init(); 
	bfs(n);
	return 0;
}
void init()
{
//	memset(a,0,sizeof(a);
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		a[i].value = a[i].no = i;
	}
	cnt = ct = n+1;
} 
void bfs(int d)
{
	if(d == 1)
	{
		puts("ed");
		for(int i = 1;i < ct;i++)if(!b[i]) 
		{
			Pr(i);
		}
		return; 
	}
	for(int i = 1;i < ct;i++)if(!b[i])
	{
		for(int j = 1;j < ct;j++)if(!b[j])if(i!=j)
		{
			pa t;//判重 
			toTr tt;//构造新节点 
			tt.soLe= a[i].no,t.first = a[i].value,tt.soRi = a[j].no, t.second = a[j].value;
			if(!un[t])//map 应该是0吧 不一定正确的剪枝 已经枚举过的节点不再枚举 
			{
				tt.value = cnt;
				tt.no = ct;
				a[ct] = tt;//添加一个节点 
				b[j] = b[i] = 1;//删除两个 
				un[t] = 1;//判重 
//				toTr tp = a[i];
				cnt++;
				ct++;
//				printf("d:%d ct:%d cnt:%d no:%d va:%d sl:%d sr:%d\n",d,ct,cnt,a[ct].no,a[ct].value,a[ct].soLe,a[ct].soRi);
				bfs(d-1);
				ct--;
				b[j] = b[i] = 0;//撤销操作 
//				a[ct] = tp;
			}
		}
	}
}
void Pr(int n)
{
	printf("%d:%3d ",n,a[n].value);
	int t = a[n].soLe;
	if(t)Pr(t);
	else putchar(65);
	putchar('\n');
	t = a[n].soRi;
	if(t)Pr(t);
	else putchar(65);
}