#include <bits/stdc++.h>
using namespace std;
const int maxn = 11;

vector<int> getPermutation(vector<int> T) {
    int n = T.size();
    vector<int> P(n);
    iota(P.begin(), P.end(), 0);
    for (int i = 0; i < n; i++) {
        if (T[i] != i)
            swap(P[T[i]], P[i]);
    }
    return P;
}
vector<vector<int>> cycles(vector<int> P) {
    vector<vector<int>> ans;
    int n = P.size();
    vector<bool> vis(n);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            ans.emplace_back();
            for (int x = i; !vis[x]; x = P[x]) {
                ans.back().push_back(x);
                vis[x] = true;
            }
        }
    }
    return ans;
}
int cnt;
void dfs(int i, int n, int now) {
    static int T[maxn];
    if (i == n) {
        ++cnt;
        vector<int> P = getPermutation(vector<int>(T, T+n));
        vector<vector<int>> C = cycles(P);

        cout << "T = ";
        for (int i = 0; i < n; i++)
            cout << T[i]+1 << ' ';
        cout << '\t';
        cout << "P = ";
        for (int i = 0; i < n; i++)
            cout << P[i]+1 << ' ';
        cout << '\t';
        for (vector<int> c: C) {
            cout << "( ";
            for (int x: c) cout << x + 1 << ' ';
            cout << ")";
        }
        cout << '\n';

        return;
    }
    for (int j = now; j <= i; j++) {
        T[i] = j;
        dfs(i+1, n, j);
    }
}
int main() {
    int n = 4;
    cout << "n = " << n << '\n';
    cnt = 0;
    dfs(0, n, 0);
    cout << "cnt = " << cnt<<'\n';
}