#include <bits/stdc++.h>
#include "Ali.h"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second
#define ff first
#define ss second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
typedef complex<double> ftype;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
*/
//-------------------------------------------
const int B = 7;
const int MAXN = 1e4 + 10;
vector<int> gr[MAXN], g[MAXN], comps[MAXN];
int color[MAXN];
int recolor[MAXN];
int clr = 0;
vector<int> all_roots;
int roots[MAXN];
int dfs(int v, int start, int p = -1){
int siz = 1;
for (int u: gr[v]){
if (u != p){
siz += dfs(u, start, v);
}
}
if (siz >= 7 || v == start){
all_roots.push_back(v);
return 0;
} else {
if (p != -1){
g[v].push_back(p);
g[p].push_back(v);
}
return siz;
}
}
void coloring(int v, int c, int p = -1){
color[v] = c;
for (int u: g[v]){
if (u != p)
coloring(u, c, v);
}
}
void bfsRecolor(int v0){
deque<pt> q;
q.push_back({v0, -1});
int currColor = 0;
while (!q.empty()){
auto [v, p] = q.front();
q.pop_front();
recolor[v] = currColor++;
for (int u: comps[v]){
if (u != p)
q.push_back({u, v});
}
}
}
int id[MAXN];
void indexing(int v, int &num, int comp, int p = -1){
id[v] = comp * (2 * B - 1) + num;
num++;
for (int u: g[v]){
if (u != p)
indexing(u, num, comp, v);
}
}
int n;
void Init(int N, vector<int> U, vector<int> V){
n = N;
for (int i = 0; i < n; i++)
gr[i].clear(), g[i].clear();
for (int i = 0; i < n - 1; i++){
int u, v;
u = U[i], v = V[i];
gr[u].push_back(v);
gr[v].push_back(u);
}
int start = 0;
for (; start < n && sz(gr[start]) == 3; start++);
all_roots.clear();
dfs(start, start);
fill(color, color + n, -1);
clr = 0;
for (int i = 0; i < n; i++){
if (color[i] == -1)
coloring(i, clr++);
}
for (int i = 0; i < n; i++)
comps[i].clear();
for (int u = 0; u < n; u++){
for (int v: gr[u]){
if (color[u] != color[v])
comps[color[u]].push_back(color[v]);
}
}
fill(recolor, recolor + n, -1);
bfsRecolor(0);
for (int i = 0; i < n; i++){
color[i] = recolor[color[i]];
}
fill(roots, roots + n, 0);
for (int x: all_roots)
roots[color[x]] = x;
for (int rt = 0; rt < clr; rt++){
int num = 0;
indexing(roots[rt], num, rt);
}
set<int> ids;
for (int i = 0; i < n; i++)
ids.insert(id[i]);
for (int i = 0; i < n; i++){
SetID(i, id[i]);
}
}
string encode(ll x, int len){
string res;
for (; x > 0; x /= 2){
res += (char)(x % 2 + '0');
}
while (sz(res) < len)
res += '0';
reverse(all(res));
return res;
}
ll decode(const string &s){
ll ans = 0;
for (char c: s){
int val = (c - '0');
ans = ans * 2 + val;
}
return ans;
}
void encodeComponent(int v, string &res, int p = -1){
for (int u: g[v]){
if (u != p){
res += '1';
encodeComponent(u, res, v);
res += '0';
}
}
}
bool find_path(int v, int to, vector<int> &path, int p = -1){
path.push_back(v);
if (v == to){
return true;
}
for (int u: gr[v]){
if (u != p){
if (find_path(u, to, path, v))
return true;
}
}
path.pop_back();
return false;
}
pt parse(ll y){
ll x = 1;
while (y >= x){
y -= x;
x++;
}
x--;
return {x, y};
}
string SendA(string s){
auto [x, y] = parse(decode(s));
string t1, t2;
encodeComponent(roots[x], t1);
encodeComponent(roots[y], t2);
int d = 0;
int num1, num2;
num1 = num2 = 0;
if (x != y){
int p1 = 0, p2 = 0;
for (int i = 0; i < n; i++){
if (color[i] == x)
p1 = i;
if (color[i] == y)
p2 = i;
}
vector<int> path;
find_path(p1, p2, path);
for (int i = 0; i < 2; i++){
while (color[path[sz(path) - 1]] == color[path[sz(path) - 2]])
path.pop_back();
reverse(all(path));
}
d = sz(path) - 1;
num1 = id[path[0]] % (2 * B - 1);
num2 = id[path.back()] % (2 * B - 1);
}
while (sz(t1) < 25)
t1.push_back('0');
while (sz(t2) < 25)
t2.push_back('0');
string ret = encode(d, 14) + t1 + t2 + encode(num1, 4) + encode(num2, 4);
return ret;
}
#include <bits/stdc++.h>
#include "Benjamin.h"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second
#define ff first
#define ss second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
typedef complex<double> ftype;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
*/
//-------------------------------------------
int x2, y2;
const int B1 = 7;
vector<int> T1[2 * B1];
vector<int> T2[2 * B1];
void buildT1(int v, string &s, int &fr){
while (s.back() == '1'){
int u = fr++;
T1[v].push_back(u);
T1[u].push_back(v);
s.pop_back();
buildT1(u, s, fr);
}
s.pop_back();
}
void buildT2(int v, string &s, int &fr){
while (s.back() == '1'){
int u = fr++;
T2[v].push_back(u);
T2[u].push_back(v);
s.pop_back();
buildT2(u, s, fr);
}
s.pop_back();
}
int find_dst1(int v, int to, int c, int p = -1){
if (v == to)
return c;
for (int u: T1[v]){
if (u != p){
int tmp = find_dst1(u, to, c + 1, v);
if (tmp != -1)
return tmp;
}
}
return -1;
}
int find_dst2(int v, int to, int c, int p = -1){
if (v == to)
return c;
for (int u: T2[v]){
if (u != p){
int tmp = find_dst2(u, to, c + 1, v);
if (tmp != -1)
return tmp;
}
}
return -1;
}
string encode1(ll x, int len){
string res;
for (; x > 0; x /= 2){
res += (char)(x % 2 + '0');
}
while (sz(res) < len)
res += '0';
reverse(all(res));
return res;
}
ll decode1(const string &s){
ll ans = 0;
for (char c: s){
int val = (c - '0');
ans = ans * 2 + val;
}
return ans;
}
string SendB(int N, int X, int Y){
int x = X;
int y = Y;
x2 = x;
y2 = y;
x /= (2 * B1 - 1);
y /= (2 * B1 - 1);
if (x < y)
swap(x, y), swap(x2, y2);
return encode1(x * (x + 1) / 2 + y, 20);
}
int Answer(string s){
int d = decode1(s.substr(0, 14));
string t1 = s.substr(14, 25);
string t2 = s.substr(39, 25);
int num1 = decode1(s.substr(64, 4));
int num2 = decode1(s.substr(68, 4));
reverse(all(t1));
reverse(all(t2));
for (int i = 0; i < 2 * B1; i++)
T1[i].clear(), T2[i].clear();
int fr = 1;
buildT1(0, t1, fr);
fr = 1;
buildT2(0, t2, fr);
int u = x2 % (2 * B1 - 1);
int v = y2 % (2 * B1 - 1);
int ans = 0;
if (x2 / (2 * B1 - 1) == y2 / (2 * B1 - 1)){
ans = find_dst1(u, v, 0);
} else {
int d1 = find_dst1(u, num1, 0);
int d2 = find_dst2(v, num2, 0);
ans = d1 + d2 + d;
}
return ans;
}
