#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
int n;
vector<int> al[250000];
ll in[250000];
ll out[250000];
int TIME=0;
void dfs(int i,int p){
in[i]=TIME;
for (auto &it:al[i]){
if (it==p) continue;
dfs(it,i);
}
out[i]=TIME++;
Code(i,in[i]*250000+out[i]);
}
void Encode(int N, int A[], int B[]){
n=N;
rep(x,0,n-1){
al[A[x]].pub(B[x]);
al[B[x]].pub(A[x]);
}
dfs(0,-1);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
void InitDevice()
{
}
int Answer(long long S, long long T){
ll sin=S/250000,sout=S%250000;
ll tin=T/250000,tout=T%250000;
if (sin<=tin && tout<=sout) return 1;
if (tin<=sin && sout<=tout) return 0;
return 2;
}
