#include "Ali.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

namespace {

int N, nn;
vector<bool> ig;
vector<vector<pair<int, int>>> g;
vector<vector<int>> group;
vector<pair<int, int>> lab;
vector<int> par, dep, sz, lst;

vector<string> six = {
    "000011001111",
    "000010110111",
    "000001110111",
    "000000111111",
    "000001011111",
    "000011100111",
    "000101100111",
    "000011011011",
    "000001111011",
    "000001101111",
    "000010111011",
};

int dfs1(int u, int p) {
    int sz = 1;
    for (auto [v, id] : g[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        int val = dfs1(v, u);
        if (val >= 7) ig[id] = true;
        else sz += val;
    }
    return sz;
}

void get_group(int u, int p) {
    sz[u] = 1;
    lab[u] = {isz(group) - 1, isz(group.back())};
    group.back().emplace_back(u);
    for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
        par[v] = lab[u].second;
        get_group(v, u);
        sz[u] += sz[v];
        lst[u] = lst[v];
    }
    if (lst[u] == -1) lst[u] = u;
}

void add_nodes(int u) {
    int cnt = 0;
    for (auto [v, id] : g[u]) if (not ig[id]) {
        ++cnt;
        int clst = lst[v];
        while (sz[v] < 6) {
            g.emplace_back();
            ig.emplace_back(0);
            g[clst].emplace_back(nn, nn - 1);
            g[nn].emplace_back(clst, nn - 1);
            clst = nn, sz[v]++, nn++;
        }
    }
    while (cnt < 2) {
        int clst = u;
        for (int i = 0; i < 6; ++i) {
            g.emplace_back();
            ig.emplace_back(0);
            g[clst].emplace_back(nn, nn - 1);
            g[nn].emplace_back(clst, nn - 1);
            clst = nn, nn++;
        }
        ++cnt;
    }
}

int get_centroid() {
    vector<int> sz(N);
    auto dfs_sz = [&](auto self, int u, int p) -> void {
        sz[u] = 1;
        for (auto [v, id] : g[u]) if (v != p) {
            self(self, v, u);
            sz[u] += sz[v];
        }
    };
    dfs_sz(dfs_sz, 0, -1);
    auto dfs_cen = [&](auto self, int u, int p) -> int {
        for (auto [v, id] : g[u]) if (v != p) {
            if (sz[v] > sz[0] / 2) return self(self, v, u);
        }
        return u;
    };
    int root = dfs_cen(dfs_cen, 0, -1);
    queue<int> q;
    vector<int> vis(N);
    q.emplace(root);
    vis[root] = true;
    while (not q.empty()) {
        int u = q.front();
        if (isz(g[u]) < 3) {
            root = u;
            break;
        }
        q.pop();
        for (auto [v, id] : g[u]) if (not vis[v]) {
            q.emplace(v);
            vis[v] = true;
        }
    }
    vis.assign(N, -1);
    q = queue<int>();
    vis[root] = 0;
    q.emplace(root);
    while (not q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [v, id] : g[u]) if (vis[v] == -1) {
            vis[v] = vis[u] + 1;
            q.emplace(v);
        }
    }
    assert(*max_element(all(vis)) <= 5000);
    return root;
}

int callitacheck(int u, int p) {
    int sz = 1;
    for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
        int val = callitacheck(v, u);
        if (p == -1) assert(val == 6);
        sz += val;
    }
    if (p == -1) assert(sz == 13);
    return sz;
}

string get_hash(int u, int p) {
    vector<string> vec;
    for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
        vec.push_back(get_hash(v, u));
    }
    sort(all(vec));
    string res = "";
    res.push_back('0');
    for (auto s : vec) res += s;
    res.push_back('1');
    return res;
};

array<int, 3> bfs(int gX, int gY) {
    queue<int> q;
    vector<int> trace(N, -1), d(N, -1);
    d[group[gX][0]] = 0;
    q.emplace(group[gX][0]);
    while (not q.empty()) {
        auto u = q.front(); q.pop();

        if (lab[u].first == gY) {
            int len = 0, ou = u;
            while (lab[u].first != gX) {
                u = trace[u];
                ++len;
            }
            return {u, ou, len};
        }

        for (auto [v, id] : g[u]) {
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                trace[v] = u;
                q.emplace(v);
            }
        }
    }
}

void dfs2(int u, int p, int d) {
    lab[u].first = d;
    for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
        dfs2(v, u, d + 1);
    }
}

}

void Init(int N, vector<int> U, vector<int> V) {
    ::N = N;
    g.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
        int u = U[i], v = V[i];
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    dep.assign(N, 0);
    ig.assign(N - 1, false);
    int root = get_centroid();
    dfs1(root, -1);

    nn = N;
    vector<int> avec(N);
    iota(all(avec), 0);
    sort(all(avec), [&](int x, int y) {
        return dep[x] < dep[y];
    });
    group.clear();
    sz.assign(N, 0);
    lst.assign(N, -1);
    par.assign(N, -1);
    lab.assign(N, {-1, -1});
    for (int i : avec) if (lab[i].first == -1) {
        group.emplace_back();
        get_group(i, -1);
        add_nodes(i);
        // get_hash(i, -1);
        // callitacheck(i, -1);
    }

    for (int i = 0; i < N; ++i) {
        // cout << i << " " << lab[i].first * 13 + lab[i].second << endl;
        SetID(i, lab[i].first * 13 + lab[i].second);
    }
}

string SendA(string S) {
    int val = 0, cnt = 0;
    for (int i = 0; i < 20; ++i) {
        val += (S[i] - '0') << i;
    }
    int gX = -1, gY = -1;
    for (int i = 0; i < 1429; ++i) for (int j = i; j < 1429; ++j) {
        if (val == cnt) gX = i, gY = j;
        ++cnt;
    }

    if (gX == gY) {
        string res = "";
        for (auto u : group[gX]) for (int i = 0; i < 4; ++i) {
            res.push_back((par[u] >> i & 1) + '0');
        }
        return res;
    }

    auto [vX, vY, len] = bfs(gX, gY);
    dfs2(vX, -1, 0); dfs2(vY, -1, 0);

    string res = "";

    sort(all(group[gX]), [&](const auto &lhs, const auto &rhs) {
        return lab[lhs].second < lab[rhs].second;
    });
    for (auto u : group[gX]) for (int i = 0; i < 4; ++i) {
        res.push_back((lab[u].first >> i & 1) + '0');
    }
    while (isz(res) < 52) res.push_back('0');

    sort(all(group[gY]), [&](const auto &lhs, const auto &rhs) {
        return lab[lhs].second < lab[rhs].second;
    });
    for (auto u : group[gY]) for (int i = 0; i < 4; ++i) {
        res.push_back((lab[u].first >> i & 1) + '0');
    }
    while (isz(res) < 104) res.push_back('0');

    for (int i = 0; i < 14; ++i) {
        res.push_back((len >> i & 1) + '0');
    }

    return res;
}

#include "Benjamin.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

namespace {

int gX, nX, gY, nY;

}

string SendB(int N, int X, int Y) {
	if (X > Y) swap(X, Y);

	gX = X / 13, nX = X % 13;
	gY = Y / 13, nY = Y % 13;

	int val = -1, cnt = 0;
	for (int i = 0; i < 1429; ++i) for (int j = i; j < 1429; ++j) {
		if (i == gX and j == gY) val = cnt;
		++cnt;
	}

	string res = "";
	for (int i = 0; i < 20; ++i) {
		res.push_back((val >> i & 1) + '0');
	}
	return res;
}

int Answer(string T) {
	int res = 0;

	if (gX == gY) {
		int N = isz(T) / 4;
		vector<vector<int>> g(N);
		for (int i = 1; i < N; ++i) {
			int p = 0;
			for (int j = 0; j < 4; ++j) {
				p += (T[i * 4 + j] - '0') << j;
			}
			g[p].emplace_back(i);
			g[i].emplace_back(p);
		}
		vector<int> d(N, -1);
		queue<int> q;
		d[nX] = 0;
		q.emplace(nX);
		while (not q.empty()) {
			auto u = q.front(); q.pop();
			for (auto v : g[u]) if (d[v] == -1) {
				d[v] = d[u] + 1;
				q.emplace(v);
			}
		}
		return d[nY];
	}

	// cout << gX << " " << gY << " " << nX << " " << nY << endl;

	for (int i = nX * 4; i < (nX + 1) * 4; ++i) {
		res += (T[i] - '0') << (i - nX * 4);
	}
	for (int i = 52 + nY * 4; i < 52 + (nY + 1) * 4; ++i) {
		res += (T[i] - '0') << (i - 52 - nY * 4);
	}
	for (int i = 104; i < 104 + 14; ++i) {
		res += (T[i] - '0') << (i - 104);
	}
	return res;
}