#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;
vector<bool> ig;
vector<vector<pair<int, int>>> g;
vector<vector<int>> group;
vector<pair<int, int>> lab;
vector<int> par; 

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

void get_group(int u, int p) {
    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);
    }
}

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);
    }

    ig.assign(N - 1, false);
    int root = -1;
    for (int i = 0; i < N; ++i) if (isz(g[i]) == 1) {
        root = i;
        break;
    }
    dfs1(0, -1);

    group.clear();
    par.assign(N, -1);
    lab.assign(N, {-1, -1});
    for (int i = 0; i < N; ++i) if (lab[i].first == -1) {
        group.emplace_back();
        get_group(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);
    // cout << vX << " " << vY << " " << len << endl;

    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];
	}

	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;
}