#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
void Encode(int N, int A[], int B[]) {
auto EncodePair = [&](int u, int v) -> long long { // u <= v
static const int MAX = 250005;
static vector<long long> num(MAX);
static bool first = true;
if (first) {
num[0] = MAX;
for (int i = 1; i < MAX; i++) {
num[i] = MAX - i;
num[i] += num[i - 1];
}
}
first = false;
return (u > 0 ? num[u - 1] : 0) + (v - u);
};
auto DecodePair = [&](long long x) -> pair<int, int> { // u <= v
static const int MAX = 250005;
int lo = 0, hi = MAX - 1, u, v;
while (lo < hi) {
int md = (lo + hi + 1) / 2;
if (EncodePair(md, md) <= x) {
lo = md;
} else {
hi = md - 1;
}
}
u = lo;
lo = u, hi = MAX - 1;
while (lo < hi) {
int md = (lo + hi + 1) / 2;
if (EncodePair(u, md) <= x) {
lo = md;
} else {
hi = md - 1;
}
}
v = lo;
return {u, v};
};
vector<vector<int>> adj(N);
for (int i = 0; i + 1 < N; i++) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
int timer = 0;
vector<int> st(N), et(N);
function<void(int, int)> Dfs = [&](int u, int p) {
st[u] = timer++;
for (auto v : adj[u]) if (v != p) {
Dfs(v, u);
}
et[u] = timer - 1;
};
Dfs(0, -1);
for (int i = 0; i < N; i++) {
Code(i, EncodePair(st[i], et[i]));
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice() {}
int Answer(long long S, long long T) {
auto EncodePair = [&](int u, int v) -> long long { // u <= v
static const int MAX = 250005;
static vector<long long> num(MAX);
static bool first = true;
if (first) {
num[0] = MAX;
for (int i = 1; i < MAX; i++) {
num[i] = MAX - i;
num[i] += num[i - 1];
}
}
first = false;
return (u > 0 ? num[u - 1] : 0) + (v - u);
};
auto DecodePair = [&](long long x) -> pair<int, int> { // u <= v
static const int MAX = 250005;
int lo = 0, hi = MAX - 1, u, v;
while (lo < hi) {
int md = (lo + hi + 1) / 2;
if (EncodePair(md, md) <= x) {
lo = md;
} else {
hi = md - 1;
}
}
u = lo;
lo = u, hi = MAX - 1;
while (lo < hi) {
int md = (lo + hi + 1) / 2;
if (EncodePair(u, md) <= x) {
lo = md;
} else {
hi = md - 1;
}
}
v = lo;
return {u, v};
};
int stx, etx, sty, ety;
tie(stx, etx) = DecodePair(S);
tie(sty, ety) = DecodePair(T);
if (sty <= stx && etx <= ety) {
return 0;
} else if (stx <= sty && ety <= etx) {
return 1;
} else {
return 2;
}
}
