#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;

void Encode(int n, int U[], int V[]) {
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
    constexpr int B = 30;
    constexpr int A0 = 6, A1 = 14;
    vector<int> code(n), siz(n), type(n), father(n), tin(n), tout(n);
    vector<vector<int>> g(n);
    auto dfs = [&](auto self, int v) -> void {
        siz[v] = 1;
        vector<int> nxt;
        for (int to : adj[v]) {
            adj[to].erase(std::find(adj[to].begin(), adj[to].end(), v));
            self(self, to);
            siz[v] += siz[to];
        }
        type[v] = siz[v] >= B;
        for (int to : adj[v]) {
            if (siz[to] < B && type[v] == 1) {
                nxt.push_back(to);
            } else {
                g[v].push_back(to);
            }
        }
        if (type[v] == 0) {
            return;
        }
        vector<int> stk;
        int sum_stk = 0;
        for (int x : nxt) {
            stk.push_back(x);
            sum_stk += siz[x];
            if (sum_stk >= B) {
                int new_vertex = size(tin);
                g.push_back(stk);
                g[v].push_back(new_vertex);
                tin.push_back({}), tout.push_back({});
                type.push_back(1);
                stk.clear();
                sum_stk = 0;
            }
        }
        g[v].insert(g[v].end(), stk.begin(), stk.end());
        sum_stk = 0;
    };
    dfs(dfs, 0);

    int cnt[2]{};
    auto gfs = [&](auto self, int v, int last) -> void {
        tin[v] = cnt[type[v]];
        cnt[type[v]] += 1;
        if (type[v] == 1) {
            for (int to : g[v]) {
                if (type[to] == 1) {
                    self(self, to, v);
                }
            }
            cnt[0] = 0;
            for (int to : g[v]) {
                if (type[to] == 0) {
                    self(self, to, v);
                }
            }
        } else {
            father[v] = last;
            for (int to : g[v]) {
                self(self, to, last);
            }
        }
        tout[v] = cnt[type[v]];
    };
    gfs(gfs, 0, 0);
    int mx = 0;
    for (int i = 0; i < g.size(); ++i) {
        if (type[i] == 1) {
            mx = max(mx, tout[i]);
        }
    }
    if ((1 << A1) <= mx) {
        return;
    }
    assert((1 << A1) > mx);
    for (int v = 0; v < n; ++v) {
        if (type[v] == 1) {
            code[v] = ((((tout[v] - tin[v]) << A1) + tin[v]) << 1) + 1;
        } else {
            code[v] = (((((tin[father[v]] << A0) + tout[v] - tin[v]) << A0) + tin[v]) << 1) + 0;
        }
//        if (v == 3 || v == 21) {
//            cout << v << ":\n";
//            cout << tin[v] << " " << tout[v] << " " << type[v] << " " << siz[v] << " " << father[v] << endl;
//        }
//        cerr << code[v] << " \n"[v == n - 1];
    }
    for (int i = 0; i < n; ++i) {
        Code(i, code[i]);
    }
}

#include "Device.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int B = 30;
constexpr int A0 = 7, A1 = 14;

array<int, 3> query(long long S) {
    if (S % 2 == 0) {
        S /= 2;
        int tin = S & ((1 << A0) - 1);
        int tout = tin + ((S >> A0) & ((1 << A0) - 1));
        int father = (S >> (2 * A0));
        return {tin, tout, father};
    } else {
        S /= 2;
        int tin = S & ((1 << A1) - 1);
        int tout = tin + ((S >> A1) & ((1 << A1) - 1));
        return {tin, tout, -1};
    }
}

void InitDevice() {
}

int Answer(long long S, long long T) {
    auto a = query(S);
    auto b = query(T);
    if (S % 2 == T % 2) {
        if (S % 2 == 0 && a[2] != b[2]) {
            return 2;
        }
        if (a[0] <= b[0] && a[1] >= b[1]) {
            return 1;
        } else if (b[0] <= a[0] && b[1] >= a[1]) {
            return 0;
        } else {
            return 2;
        }
    } else {
        if (S % 2 == 0) {
            if (b[0] <= a[2] && b[1] > a[2]) {
                return 0;
            } else {
                return 2;
            }
        } else {
            if (a[0] <= b[2] && a[1] > b[2]) {
                return 1;
            } else {
                return 2;
            }
        }
    }
    return 0;
}