#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;
vector<int> adj[250005];
lint low[250005], high[250005];
lint cnt = 0;
void dfs(int u, int p){
high[u] = low[u] = cnt++;
for(int v : adj[u]){
if(v == p) continue;
dfs(v, u);
high[u] = high[v];
}
}
void Encode(int n, int A[], int B[]){
for(int i = 0;i < n-1;i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(0, -1);
for(int i = 0; i < n; ++i){
Code(i, low[i]*250000LL+high[i]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;
void InitDevice(){
}
int Answer(long long S, long long T){
lint slow = S/250000;
lint shigh = S%250000;
lint tlow = T/250000;
lint thigh = T%250000;
if(slow <= tlow and thigh <= shigh) return 1;
else if(tlow <= slow and shigh <= thigh) return 0;
return 2;
}
