#include <bits/stdc++.h>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (int i = (r); i >= (l); --i)
#define popc(x) __builtin_popcount(x)
#define allc(x) (x).begin(), (x).end()
#define SZ(v) (int)v.size()
#define PII pair<int, int>
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using u128 = unsigned __int128;
const int N = 150;
u128 f[N][N], ans;
vector<int> G[N];
int step, n;
void dfs(int u, int dep) {
    for (int v: G[u]) {
        ++step;
        dfs(v, dep + 1);
        ans += f[2 * n - 3 - step][dep + 2];
        ++step;
    }
}
u128 encoder(int N, const int *p) {
    n = N;
    if (!f[0][0]) {
        f[0][0] = 1;
        FOR (i, 1, 138) {
            FOR (j, 0, min(i, 70)) {
                f[i][j] = f[i - 1][j + 1];
                if (j) {
                    f[i][j] += f[i - 1][j - 1];
                }
            }
        }
    }
    step = 0;
    ans = 0;
    FOR (i, 1, n) {
        G[i].clear();
    }
    FOR (i, 2, n) {
        G[p[i]].PB(i);
    }
    dfs(1, 0);
    return ans;
}
int stk[N];
void decoder(int N, u128 M, int *p) {
    n = N;
    ans = M;
    if (!f[0][0]) {
        f[0][0] = 1;
        FOR (i, 1, 138) {
            FOR (j, 0, min(i, 70)) {
                f[i][j] = f[i - 1][j + 1];
                if (j) {
                    f[i][j] += f[i - 1][j - 1];
                }
            }
        }
    }
    int dep = 0, all = 1, cnt1 = 0;
    p[1] = 0;
    stk[0] = 1;
    FOR (step, 1, 2 * n - 3) {
        u128 to_add = f[2 * n - 2 - step][dep + 1];
        if (ans >= to_add) {
            ans -= to_add;
            --dep;
        } else {
            p[++all] = stk[dep];
            stk[++dep] = all;
        }
    }
}