#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace {
const int HALF = 125000;
const int MAXN = 250000;
ll enc(int a, int b) {
if(!a) return b;
assert(b<=2*a); assert(b>=a);
if(a<HALF) {return ll(a)*(a+1)/2 + MAXN + 5 + (b-a);}
a = MAXN - a;
b = MAXN - b;
return 7.813e9 + ll(a)*(a+1)/2+ b;
}
vector<int> adj[250005];
int sub[250005];
int dfs1(int x, int p) {
sub[x]=1;
for(auto i: adj[x]) if(i!=p) {sub[x]+=dfs1(i,x);}
if(adj[x].size()>=3) {
for(int i=1;i<adj[x].size();i++) if(adj[x][i]==p) swap(adj[x][i],adj[x][0]);
for(int i=2;i<adj[x].size();i++) if(sub[adj[x][i]]>sub[adj[x][1]]) swap(adj[x][i],adj[x][1]);
}
return sub[x];
}
int pre[250005], post[250005], cnt;
void dfs2(int x, int p) {
pre[x]=cnt;
for(auto i: adj[x]) if(i!=p) dfs2(i,x);
post[x]=cnt++;
}
}
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]);
dfs1(0,-1); dfs2(0,-1);
for (int i = 0; i < N; ++i) {
Code(i, enc(pre[i],post[i]));
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace {
const int HALF = 125000;
const int MAXN = 250000;
ll enc(int a, int b) {
if(!a) return b;
assert(b<=2*a); assert(b>=a);
if(a<HALF) {return ll(a)*(a+1)/2 + MAXN + 5 + (b-a);}
a = MAXN - a;
b = MAXN - b;
return 7.813e9 + ll(a)*(a+1)/2+ b;
}
pair<int,int> dec(ll x) {
if(x<=MAXN) return {0,x};
if(x<7.813e9) {
ll hi = x - MAXN - 5;
int l = 0, h = 250000;
while(h-l>1) {
int m = (l+h)/2;
if(ll(m)*(m+1)/2 <= hi) l=m;
else h=m;
}
return {l,hi - ll(l)*(l-1)/2};
}
// this problem tastes like complex bashing
ll hi = x - 7.813e9;
int l = 0, h = 250000;
while(h-l>1) {
int m = (l+h)/2;
if(ll(m)*(m+1)/2 <= hi) l=m;
else h=m;
}
return {MAXN-l,MAXN-(hi-ll(l)*(l+1)/2)};
}
}
void InitDevice()
{
}
int Answer(long long S, long long T)
{
pair<int,int> s = dec(S), t = dec(T);
if(s.first<=t.first&&s.second>=t.second) return 1;
if(t.first<=s.first&&t.second>=s.second) return 0;
return 2;
}
