#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 = 100;
    constexpr int A0 = 8, 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]);
        }
    }
    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;
        }
//        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 = 100;
constexpr int A0 = 7, A1 = 14;
#include "Device.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int B = 100;
constexpr int A0 = 8, 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 (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;
}

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

Device.code:13:15: error: redefinition of ‘constexpr const int B’
   13 | constexpr int B = 100;
      |               ^
Device.code:6:15: note: ‘constexpr const int B’ previously defined here
    6 | constexpr int B = 100;
      |               ^
Device.code:14:15: error: redefinition of ‘constexpr const int A0’
   14 | constexpr int A0 = 8, A1 = 14;
      |               ^~
Device.code:7:15: note: ‘constexpr const int A0’ previously defined here
    7 | constexpr int A0 = 7, A1 = 14;
      |               ^~
Device.code:14:23: error: redefinition of ‘constexpr const int A1’
   14 | constexpr int A0 = 8, A1 = 14;
      |                       ^~
Device.code:7:23: note: ‘constexpr const int A1’ previously defined here
    7 | constexpr int A0 = 7, A1 = 14;
      |                       ^~
Device.code:63:15: error: redefinition of ‘std::array<int, 3> query(long long int)’
   63 | array<int, 3> query(long long S) {
      |               ^~~~~
Device.code:16:15: note: ‘std::array<int, 3> query(long long int)’ previously defined here
   16 | array<int, 3> query(long long S) {
      |               ^~~~~
Device.code:78:6: error: redefinition of ‘void InitDevice()’
   78 | void InitDevice() {
      |      ^~~~~~~~~~
Device.code:31:6: note: ‘void InitDevice()’ previously defined here
   31 | void InitDevice() {
      |      ^~~~~~~~~~
Device.code:81:5: error: redefinition of ‘int Answer(long long int, long long int)’
   81 | int Answer(long long S, long long T) {
      |     ^~~~~~
Device.code:34:5: note: ‘int Answer(long long int, long long int)’ previously defined here
   34 | int Answer(long long S, long long T) {
      |     ^~~~~~
grader.cpp: In function ‘int main(int, char**)’:
grader.cpp:62:34: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
   62 |                         printf("%d ", given_code[i]);
      |                                 ~^    ~~~~~~~~~~~~~
      |                                  |                |
      |                                  int              long long int
      |                                 %lld
grader.cpp:73:33: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
   73 |                         scanf("%d", &given_code[i]);
      |                                ~^   ~~~~~~~~~~~~~~
      |                                 |   |
      |                                 |   long long int*
      |                                 int*
      |                                %lld
grader.cpp:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |                 scanf("%d%d", &N, &Q);
      |                 ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:46:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |                         scanf("%d%d", &(A[i]), &(B[i]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
grader.cpp:49:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |                         scanf("%d%d", &(X[i]), &(Y[i]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
grader.cpp:71:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |                 scanf("%d%d", &N, &Q);
      |                 ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:73:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   73 |                         scanf("%d", &given_code[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
grader.cpp:77:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |                         scanf("%d%d", &X, &Y);
      |                         ~~~~~^~~~~~~~~~~~~~~~