#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;
}
}
*/
int read(int place) {
int ans = 0;
for(int i=0; i<10; i++) {
ans*=2;
ans += getHint(place*10+i+1);
}
return ans;
}
void write(int x, int place, int v) {
for(int i=0; i<10; i++) {
setHint(x, place*10+i+1, v&(1<<(9-i)));
}
}
vector<int> adj[1004], unreached;
void dfs(int x, int p) {
write(x, 0, p);
int counter = 0;
for(auto i : adj[x]) {
if(i==p) continue;
if(counter==0) write(x, 1, i);
else unreached.push_back(i);
dfs(x, i);
counter++;
}
if(adj[x].size()==1 && unreached.size()>0) {
write(x, 1, unreached.back());
unreached.pop_back();
}
}
void assignHints(int st, int n, int a[], int b[]) {
setHintLen(20);
for(int i=1; i<n; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
/*
for(int i=1; i<=n; i++) {
cout << i << ": ";
for(auto j : adj[i]) cout << j << ' ';
cout << '\n';
}
*/
dfs(1, 0);
/*
cout << '\n';
for(int i=1; i<=n; i++) {
current_node = i;
cout << read(0) << ' ' << read(1) << '\n';
}
cout << '\n';
*/
}
void speedrun(int st, int n, int start) {
int curr = start;
while(curr != 1) {
int par = read(0);
goTo(par);
curr = par;
//cout << "p " << curr << '\n';
}
vector<int> depth{1};
while(true) {
int child = read(1);
if(child == 0) break;
if(goTo(child)) {
depth.push_back(child);
//cout << child << '\n';
}
else {
while(true){
depth.pop_back();
goTo(depth.back());
//cout << "b " << depth.back() << ' ' << current_node << ' '<< child << '\n';
if(goTo(child)) {
depth.push_back(child);
break;
}
}
}
}
}
/*
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;
}
*/
/*
10
1 2
2 3
3 4
4 5
3 7
2 6
1 9
9 8
9 10
*/
