#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 int LG = 17;
static vector<vector<int>> adj;
static int tmr = 0;
static vector<ll> in;
static vector<ll> out;
static vector<int> prt, sub;
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];
}
}
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;
}
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(i,0,n)
{
ll c = (in[i] << LG) + out[i];
Code(i, 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 = 17;
void InitDevice()
{
}
static pair<ll, ll> getio(ll s)
{
ll in = s >> LG;
ll out = s & ((1LL << LG) - 1);
return {in, out};
}
int Answer(long long s, long long t)
{
auto [s1, t1] = getio(s);
auto [s2, t2] = getio(t);
if (s2 <= s1 && t1 <= t2) return 0;
if (s1 <= s2 && t2 <= t1) return 1;
return 2;
}
