/* Input format:
*
* N -- number of nodes
* a1 b1 -- edge 1
* ...
* a(N-1) b(N-1) -- edge N - 1
* x -- start node
*/
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
/*
static map<int, map<int, bool>> mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int>> neighbours;
void setHintLen(int l) {
if (length_set) {
cerr << "Cannot call setHintLen twice" << endl;
exit(0);
}
length = l;
length_set = true;
}
void setHint(int i, int j, bool b) {
if (!length_set) {
cerr << "Must call setHintLen before setHint" << endl;
exit(0);
}
mp[i][j] = b;
}
int getLength() { return length; }
bool getHint(int j) { return mp[current_node][j]; }
bool goTo(int x) {
if (neighbours[current_node].find(x) == end(neighbours[current_node])) {
++queries;
return false;
} else {
viz.insert(current_node = x);
return true;
}
}
*/
const int kN = 1e3;
int par[1 + kN];
vector<int> g[1 + kN];
vector<int> order;
void dfs(int u) {
order.emplace_back(u);
for (int v : g[u]) {
if (v != par[u]) {
par[v] = u;
dfs(v);
}
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
int lg = 0;
while (1 << (lg + 1) <= N) {
lg += 1;
}
lg += 1;
setHintLen(2 * lg);
for (int i = 1; i < N; ++i) {
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
dfs(1);
for (int i = 0; i < N; ++i) {
int v = order[i];
for (int bit = 0; bit < lg; ++bit) {
if (par[v] & (1 << bit)) {
setHint(v, 1 + bit, true);
}
if (i < N - 1 && (order[i + 1] & (1 << bit))) {
setHint(v, lg + 1 + bit, true);
}
}
}
}
int getPar(int x, int lg) {
int res = 0;
for (int bit = 0; bit < lg; ++bit) {
if (getHint(bit + 1)) {
res += (1 << bit);
}
}
return res;
}
int getNext(int x, int lg) {
int res = 0;
for (int bit = 0; bit < lg; ++bit) {
if (getHint(lg + 1 + bit)) {
res += (1 << bit);
}
}
return res;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
int lg = 0;
while (1 << (lg + 1) <= N) {
lg += 1;
}
lg += 1;
int l = getLength();
int curr = start;
while (curr != 1) {
int p = getPar(curr, lg);
goTo(p);
curr = p;
}
int nxt = getNext(curr, lg);
while (nxt) {
if (!goTo(nxt)) {
goTo(getPar(curr, lg));
} else {
curr = nxt;
nxt = getNext(curr, lg);
}
}
}
/*
int main() {
int N;
cin >> N;
int a[N], b[N];
for (int i = 1; i < N; ++i) {
cin >> a[i] >> b[i];
neighbours[a[i]].insert(b[i]);
neighbours[b[i]].insert(a[i]);
}
assignHints(1, N, a, b);
if (!length_set) {
cerr << "Must call setHintLen at least once" << endl;
exit(0);
}
cin >> current_node;
viz.insert(current_node);
speedrun(1, N, current_node);
if ((int)viz.size() < N) {
cerr << "Haven't seen all nodes" << endl;
exit(0);
}
cerr << "OK; " << queries << " incorrect goto's" << endl;
return 0;
}
*/
