#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
static vector < vector <int> > g;
static vector <int> idl, idr;
void dfs(int nod, int par, int &sz) {
idl[nod] = ++sz;
for(auto it : g[nod]) {
if(it != par) {
dfs(it, nod, sz);
}
}
idr[nod] = sz;
}
void Encode(int n, int A[], int B[]) {
g.resize(n);
int i;
for(i = 0; i < n - 1; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
idl.resize(n), idr.resize(n);
int sz = 0;
dfs(0, -1, sz);
vector <int> aux = idr;
sort(aux.begin(), aux.end());
aux.resize(unique(aux.begin(), aux.end()) - aux.begin());
for(i = 0; i < n; i++) {
int a = idl[i], b = lower_bound(aux.begin(), aux.end(), idr[i]) - aux.begin();
Code(i, (b << 18) + a);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice()
{
}
int Answer(long long S, long long T)
{
int ls = (S & ((1 << 18) - 1)), rs = ((S - ls) >> 18);
int lt = (T & ((1 << 18) - 1)), rt = ((T - lt) >> 18);
if(ls <= lt && rt <= rs) {
return 1;
}
if(lt <= ls && rs <= rt) {
return 0;
}
return 2;
}
