#include "Ali.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
namespace {
const int LIMIT1 = 7;
const int LIMIT2 = 13;
const int BACKET = 4;
// Memo
int Cnt = 0, Rank;
// Graph
int MainRoot = -1;
int N, U[10009], V[100009];
int dist[10009];
int Par[10009];
vector<int> G[10009];
// Group Division
int groupcnt = 0;
int group[10009]; // Group ID
int groupnum[10009]; // Vertex ID in group
int dp[10009];
vector<int> S[10009]; // Connect or Cut
vector<int> Gr[10009]; // Group Division
void AllInit() {
Cnt = 0; Rank = 0;
groupcnt = 0; MainRoot = -1;
for (int i = 0; i < 10009; i++) {
U[i] = 0; V[i] = 0; G[i].clear();
dist[i] = 0; Par[i] = 0;
group[i] = 0; groupnum[i] = 0; dp[i] = 0;
S[i].clear(); Gr[i].clear();
}
}
};
void dfs1(int pos, int par) {
dp[pos] = 1;
Par[pos] = par;
for (int to : G[pos]) {
if (to == par) continue;
dfs1(to, pos);
if (dp[to] < LIMIT1) {
S[pos].push_back(to);
S[to].push_back(pos);
dp[pos] += dp[to];
}
}
}
void dfs2(int pos, int par) {
group[pos] = groupcnt;
groupnum[pos] = (int)Gr[groupcnt].size();
Gr[groupcnt].push_back(pos);
for (int to : S[pos]) {
if (to == par) continue;
dfs2(to, pos);
}
}
void dfs3(int pos, int dep) {
dist[pos] = dep;
for (int to : G[pos]) {
if (dist[to] != -1) continue;
dfs3(to, dep + 1);
}
}
void Init(int n, vector<int> u, vector<int> v) {
AllInit();
// Initialize
N = n;
for (int i = 0; i < N - 1; i++) {
U[i] = u[i];
V[i] = v[i];
G[U[i]].push_back(V[i]);
G[V[i]].push_back(U[i]);
}
// Get Root
for (int i = 0; i < N; i++) {
if (G[i].size() == 1) { MainRoot = i; break; }
}
// Get Distance
for (int i = 0; i < N; i++) dist[i] = -1;
dfs3(MainRoot, 0);
vector<pair<int, int>> DistSort;
for (int i = 0; i < N; i++) DistSort.push_back(make_pair(dist[i], i));
sort(DistSort.begin(), DistSort.end());
// Group Division
dfs1(MainRoot, -1);
for (int i = 0; i < N; i++) group[i] = -1;
for (int i = 0; i < N; i++) {
int idx = DistSort[i].second;
if (group[idx] != -1) continue;
dfs2(idx, -1);
groupcnt += 1;
}
// Set ID
for (int i = 0; i < groupcnt; i++) {
for (int j = 0; j < (int)Gr[i].size(); j++) {
SetID(Gr[i][j], LIMIT2 * i + j);
}
}
}
string SendA(string S) {
// Get Group Number
int GX = 0, GY = 0;
for (int i = 0; i < 20; i++) {
if (S[i] == '1') Rank += (1 << i);
}
for (int i = 0; i < 1430; i++) {
for (int j = i; j < 1430; j++) {
if (Cnt == Rank) { GX = i; GY = j; }
Cnt += 1;
}
}
// Get String When GX == GY
if (GX == GY) {
string str = "";
for (int i = 0; i < N - 1; i++) {
if (group[U[i]] != GX || group[V[i]] != GY) continue;
for (int j = 0; j < BACKET; j++) {
if ((groupnum[U[i]] & (1 << j)) == 0) str += "0";
if ((groupnum[U[i]] & (1 << j)) != 0) str += "1";
}
for (int j = 0; j < BACKET; j++) {
if ((groupnum[V[i]] & (1 << j)) == 0) str += "0";
if ((groupnum[V[i]] & (1 << j)) != 0) str += "1";
}
}
return str;
}
// Get String When GX != GY
if (GX != GY) {
string str = "";
// Get GX-GY Path
bool IsSwap = false;
if (dist[Gr[GX][0]] > dist[Gr[GY][0]]) { swap(GX, GY); IsSwap = true; }
int pos = Gr[GY][0];
while (pos != -1 && group[pos] != GX) {
pos = Par[pos];
}
// Get "Representative" Vertex in Group
int u1 = Gr[GX][0]; if (pos != -1) u1 = pos;
int u2 = Gr[GY][0];
if (IsSwap == true) { swap(u1, u2); swap(GX, GY); }
// Get Distance from [Rep. of GX]
for (int i = 0; i < N; i++) dist[i] = -1;
dfs3(u1, 0);
for (int i = 0; i < (int)Gr[GX].size(); i++) {
for (int j = 0; j < BACKET; j++) {
if ((dist[Gr[GX][i]] & (1 << j)) == 0) str += "0";
if ((dist[Gr[GX][i]] & (1 << j)) != 0) str += "1";
}
}
while (str.size() < LIMIT2 * BACKET) str += "0";
// Get Distance from [Rep. of GY]
for (int i = 0; i < N; i++) dist[i] = -1;
dfs3(u2, 0);
for (int i = 0; i < (int)Gr[GY].size(); i++) {
for (int j = 0; j < BACKET; j++) {
if ((dist[Gr[GY][i]] & (1 << j)) == 0) str += "0";
if ((dist[Gr[GY][i]] & (1 << j)) != 0) str += "1";
}
}
while (str.size() < LIMIT2 * BACKET * 2) str += "0";
// Get Distance between u1 and u2
for (int i = 0; i < N; i++) dist[i] = -1;
dfs3(u1, 0);
for (int j = 0; j < 14; j++) {
if ((dist[u2] & (1 << j)) == 0) str += "0";
if ((dist[u2] & (1 << j)) != 0) str += "1";
}
return str;
}
}
#include "Benjamin.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
namespace {
const int LIMIT2 = 13;
const int BACKET = 4;
// Group
int N, X, Y;
int Cnt = 0, Rank;
int GroupX, NumX;
int GroupY, NumY;
// Graph
vector<int> G[10009];
int dist[10009];
void AllInit() {
Cnt = 0; Rank = 0;
for (int i = 0; i < 10009; i++) {
G[i].clear(); dist[i] = 0;
}
}
};
void dfs4(int pos, int dep) {
dist[pos] = dep;
for (int to : G[pos]) {
if (dist[to] != -1) continue;
dfs4(to, dep + 1);
}
}
string SendB(int n, int x, int y) {
AllInit();
N = n; X = x; Y = y;
if (X > Y) swap(X, Y);
GroupX = X / LIMIT2; NumX = X % LIMIT2;
GroupY = Y / LIMIT2; NumY = Y % LIMIT2;
// Get Rank
for (int i = 0; i < 1430; i++) {
for (int j = i; j < 1430; j++) {
if (i == GroupX && j == GroupY) Rank = Cnt;
Cnt += 1;
}
}
// Send Email
string str = "";
for (int i = 0; i < 20; i++) {
if ((Rank & (1 << i)) == 0) str += "0";
if ((Rank & (1 << i)) != 0) str += "1";
}
return str;
}
int Answer(string T) {
// If the group is same
if (GroupX == GroupY) {
for (int i = 0; i < (int)T.size() / (BACKET * 2); i++) {
int u1 = 0, u2 = 0;
for (int j = 0; j < BACKET; j++) {
if (T[i * BACKET * 2 + j] == '1') u1 += (1 << j);
if (T[i * BACKET * 2 + BACKET + j] == '1') u2 += (1 << j);
}
G[u1].push_back(u2);
G[u2].push_back(u1);
}
for (int i = 0; i < N; i++) dist[i] = -1;
dfs4(NumX, 0);
return dist[NumY];
}
// If the group is not same
if (GroupX != GroupY) {
int d1 = 0, d2 = 0, d3 = 0;
for (int i = 0; i < BACKET; i++) {
if (T[NumX * BACKET + i] == '1') d1 += (1 << i);
if (T[(LIMIT2 + NumY) * BACKET + i] == '1') d2 += (1 << i);
}
for (int i = 0; i < 14; i++) {
if (T[LIMIT2 * BACKET * 2 + i] == '1') d3 += (1 << i);
}
return d1 + d2 + d3;
}
}
