#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
// inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
// inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
const int MAX = (int)1e6;
vector<vi> g;
vll tin;
vll lol;
vll a = {};
map<ll, ll> m;
int n;
ll curr = 0LL;
ll findBest(ll x){
int l = 0;
int p = sz(a) - 1;
int mid;
while(l < p){
mid = (l + p) / 2;
if(a[mid] >= x){
p = mid;
}else{
l = mid + 1;
}
}
return a[l];
}
void dfs(int v, int p){
tin[v] = curr++;
for(auto u : g[v]){
if(u == p){
continue;
}
dfs(u, v);
}
ll now = findBest(curr - tin[v]);
lol[v] = now;
curr = tin[v] + lol[v];
}
void Encode(int N, int A[], int B[]){
n = N;
g.assign(N, vi());
tin.assign(N, 0LL);
lol.assign(N, 0LL);
for(int i = 0; i < n; i++){
g[A[i]].pb(B[i]);
g[B[i]].pb(A[i]);
}
ld x = (ld)1;
a = {1LL};
while(x <= MAX){
ll n = (ll)((ld)x * 1.05);
if(x == (ld)n){
n++;
}
a.pb(n);
x = (ld)n;
}
for(int i = 0; i < sz(a); i++){
m[a[i]] = i;
}
dfs(0, 0);
for (int i = 0; i < N; ++i) {
Code(i, (ll)sz(a) * tin[i] + m[lol[i]]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
// inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
// inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
const int MAX = (int)1e6;
vll A = {};
void InitDevice(){
ld x = (ld)1;
A = {1LL};
while(x <= MAX){
ll n = (ll)((ld)x * 1.05);
if(x == (ld)n){
n++;
}
A.pb(n);
x = (ld)n;
}
}
pll range(ll id){
return mp(id / sz(A), A[id % sz(A)]);
}
int Answer(ll S, ll T){
pll r1 = range(S);
pll r2 = range(T);
if(r1.fi >= r2.fi && r1.fi <= r2.fi + r2.se - 1){
return 0;
}else if(r2.fi >= r1.fi && r2.fi <= r1.fi + r1.se - 1){
return 1;
}else{
return 2;
}
}
