#include "Encoder.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=250002;
int n, m, k, u, v;
int stt[MAXN], fnt[MAXN], timer;
int par[MAXN], h[MAXN], sz[MAXN];
vector<int> G[MAXN];
int dfs(int node){
stt[node]=timer++;
for (int v:G[node]) if (v!=par[node]){
par[v]=node;
h[v]=h[node]+1;
sz[node]+=dfs(v);
}
fnt[node]=timer;
return ++sz[node];
}
void Encode(int _n, int A[], int B[]){
n=_n;
for (int i=0; i<n-1; i++){
u=A[i];
v=B[i];
G[u].pb(v);
G[v].pb(u);
}
dfs(0);
for (int i=0; i<n; i++){
Code(i, 1ll*stt[i]*MAXN + fnt[i]-1);
}
}
#include "Device.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=250002, LOG=60;
void InitDevice(){
}
int Answer(ll S, ll T){
int sttx=S/MAXN, fntx=S%MAXN+1;
int stty=T/MAXN, fnty=T%MAXN+1;
// debug2(sttx, fntx)
// debug2(stty, fnty)
if (stty<=sttx && fntx<=fnty) return 0;
if (sttx<=stty && fnty<=fntx) return 1;
return 2;
}
