#include "Encoder.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
static constexpr ll LG = 18;
static constexpr ll MAXN = 250000;
static vector<vector<int>> adj;
static int tmr = 0;
static vector<ll> in;
static vector<ll> out;
static vector<int> prt, sub;
static void getprt(int u, int p = -1)
{
sub[u] = 1;
prt[u] = p;
for (const auto v : adj[u])
{
if (v == p) continue;
getprt(v, u);
sub[u] += sub[v];
}
}
static void dfs(int u, int p = -1)
{
in[u] = tmr;
if (adj[u].empty())
{
out[u] = tmr;
return;
}
for (const auto v : adj[u])
{
dfs(v, u);
tmr++;
}
tmr--;
if (sz(adj[u]) == 1)
{
tmr++;
out[u] = tmr;
return;
}
out[u] = tmr;
}
static ll arith(ll l, ll r)
{
return (l + r) * (r - l + 1) / 2;
}
static ll pair2id(ll l, ll r)
{
l++; r++;
return arith(MAXN - (l - 1) + 1, MAXN) + r - l + 1; // pair id 1-indexed
}
void Encode(int n, int a[], int b[])
{
adj.resize(n);
in.resize(n);
out.resize(n);
prt.resize(n, -1);
sub.resize(n);
forn(i,0,n-1)
{
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
getprt(0);
forn(u,1,n)
{
forn(i,0,sz(adj[u]))
{
if (adj[u][i] == prt[u])
{
swap(adj[u][i], adj[u].back());
adj[u].pop_back();
break;
}
}
sort(all(adj[u]), [](int v1, int v2){ return tie(sub[v1], v1) > tie(sub[v2], v2); });
}
dfs(0);
forn(u,0,n)
{
ll c = pair2id(in[u], out[u]);
Code(u, c);
}
}
#include "Device.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
static constexpr int LG = 18;
static constexpr int MAXN = 250000;
void InitDevice()
{
}
static ll arith(ll l, ll r)
{
return (l + r) * (r - l + 1) / 2;
}
static ll pair2id(ll l, ll r)
{
l++; r++;
return arith(MAXN - (l - 1) + 1, MAXN) + r - l + 1; // pair id 1-indexed
}
static pair<ll, ll> id2pair(ll id)
{
ll sum = 0;
for (ll L = 0, R = MAXN - 1; L <= R;)
{
ll mid = (L + R) / 2;
if (pair2id(mid, mid) > id) R = mid - 1;
else if (pair2id(mid, MAXN - 1) < id) L = mid + 1;
else
{
ll id0 = pair2id(mid, mid);
return {mid, mid + id - id0};
}
}
assert(0);
return {};
}
int Answer(long long s, long long t)
{
auto [s1, t1] = id2pair(s);
auto [s2, t2] = id2pair(t);
if (s2 <= s1 && t1 <= t2) return 0;
if (s1 <= s2 && t2 <= t1) return 1;
return 2;
}
