# 某岛

… : "…アッカリ～ン . .. . " .. .
November 10, 2010

## 生成分划…

。。。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 100;
int A[N], C[N]; string SS[N];
string S;
int n;

vector<string> res;

void encode(){
/*for (int i=0;i<n;i++)
cout << A[i] << " ";
cout << endl;
*/

int m = 0;
for (int i=0;i<n;i++)
m = max(m, A[i]);
for (int i=0;i<=m;i++)
SS[i].clear();
S.clear();

for (int i=0;i<n;i++){
if (i==9) SS[A[i]] += "10";
else SS[A[i]] += char(i + 49);
SS[A[i]] += ',';
}

for (int i=0;i<=m;i++){
SS[i].erase(SS[i].size()-1);
S += "{", S += SS[i], S += "},";
}

S.erase(S.size()-1);
res.push_back(S);
}

void dfs(int k, int m){
if (k==n){
encode();
}
else {

if ((C[k]&1)==0){
for (int i=0;i<=m;i++)
A[k] = i, dfs(k+1, m);
A[k] = m+1, dfs(k+1, m+1);
}
else {

A[k] = m+1, dfs(k+1, m+1);
for (int i=m;i>=0;i--)
A[k] = i, dfs(k+1, m);
}

C[k]++;
}
}

int main(){
while (cin >> n){
res.clear();
memset(C, 0, sizeof(C));

dfs(1, 0);
cout << res.size() << endl;
for (int i=0;i<res.size();i++)
cout << res[i] << endl;
}
}