#include <bits/stdc++.h>
using namespace std;
const int maxn = 80;
unsigned __int128 f[maxn][maxn];
int A[maxn * 2], idx;
vector<int> e[maxn];
int stk[maxn * 2], n;
void init(int n) {
	f[n][n - 1] = 1;
	for (int i = n - 1; i >= 0; i--)
		for (int j = i; j >= 0; j--)
			f[i][j] = f[i + 1][j] + f[i][j + 1];
}
void dfs(int u) {
	A[++idx] = 0;
	for (auto v : e[u]) dfs(v);
	A[++idx] = 1;
}
unsigned __int128 encoder(int n, const int *p) {
	init(n);
	for (int i = 1; i <= n; i++) e[i].clear();
	for (int i = 2; i <= n; i++) e[p[i]].push_back(i);
	idx = 0;
	dfs(1);
	unsigned __int128 rk = 0;
	for (int i = 2, x = 0, y = 0; i < n * 2; i++) {
		if (A[i] == 1) rk += f[x + 1][y], y++;
		else x++;
	}
	return rk + 1;
}
void decoder(int n,unsigned  __int128 M, int *p) {
	init(n);
	unsigned __int128 rk = 0;
	A[1] = 0;
	for (int i = 2, x = 0, y = 0; i < n * 2; i++) {
		if (rk + f[x + 1][y] >= M) A[i] = 0, x++;
		else rk += f[x + 1][y], A[i] = 1, y++;
	}
	A[n * 2] = 1;
	int u = 0, top = 0;
	for (int i = 1; i <= n * 2; i++) {
		if (A[i] == 0) stk[++top] = ++u, p[u] = stk[top - 1];
		else top--;
	}
}