#include "Encoder.h"
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "../debug.h"
#else
#define debug(...) void(23)
#endif
__int128_t comb(int x, int y) {
__int128_t res = 1;
for (int i = y + 1; i <= x; ++i) {
res *= i;
}
for (int i = 1; i <= x - y; ++i) {
res /= i;
}
return res;
}
void Encode(int N, int A[], int B[]) {
// for (int i = 0; i < N; ++i) {
// Code(i, 0LL);
// }
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < N - 1; ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
std::vector<int> dep(N), par(N);
auto dfs = [&](auto&& self, int v) -> void {
for (auto u : adj[v]) {
if (u == par[v]) {
continue;
}
par[u] = v;
dep[u] = dep[v] + 1;
self(self, u);
}
};
dfs(dfs, 0);
debug(dep);
const int D = *std::max_element(dep.begin(), dep.end()) + 1;
std::vector<std::vector<int>> nodes(D);
for (int i = 0; i < N; ++i) {
nodes[dep[i]].emplace_back(i);
}
int used = 0;
std::vector<int> codes(N);
for (int d = 1; d < D; ++d) {
int n = int(nodes[d].size());
for (int x = 1; ; ++x) {
bool good = false;
for (int i = 1; i <= x; ++i) {
__int128_t cnt = comb(x, i);
if (cnt >= n) {
debug(x, i);
good = true;
int j = 0;
for (int m = 0; m < (1 << x); ++m) {
if (__builtin_popcount(m) != i) {
continue;
}
int v = nodes[d][j];
codes[v] = codes[par[v]] | (m << used);
j += 1;
if (j == n) {
break;
}
}
break;
}
}
if (good) {
used += x;
break;
}
}
}
for (int v = 0; v < N; ++v) {
Code(v, codes[v]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
#ifdef DEBUG
// #include "../debug.h"
#else
#define debug(...) void(23)
#endif
void InitDevice() {
}
int Answer(long long S, long long T) {
if (S > T && (S & T) == T) {
return 0;
}
if (S < T && (S & T) == S) {
return 1;
}
return 2;
}
