#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
namespace{
int counter=0, val=0, phase=0, tempval;
vector<int> dist, done, notdone;
vector<bool> del;
vector<deque<pii> > graph;
}
void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c){
done.clear();
dist.clear();
graph.clear();
del.clear();
del.resize(n, 0);
done.resize(1, 0);
dist.resize(n, INT_MIN/2);
graph.resize(n);
dist[0]=counter=val=phase=0;
del[0]=1;
for (int i=1; i<n; ++i)notdone.pb(i);
for (int i=0; i<a; ++i){
graph[u[i]].pb(mp(c[i], v[i]));
graph[v[i]].pb(mp(c[i], u[i]));
}
for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
}
void ReceiveA(bool x){
++counter;
val=val*2+x;
if (!phase&&counter==9){
int dj=INT_MAX/2, best;
for (auto node:done){
while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
if (graph[node].empty())continue;
if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
}
if (dj-*max_element(dist.begin(), dist.end())<val){
SendA(0);
dist[best]=dj;
done.pb(best);
del[best]=1;
int id=0;
for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
notdone.erase(find(notdone.begin(), notdone.end(), best));
for (int i=(int)log2(notdone.size()+1); i>=0; --i)SendA((1<<i)&id);
for (int i=8; i>=0; --i)SendA((1<<i)&(dj-*max_element(dist.begin(), dist.end())));
}
else{
SendA(1);
phase=1;
}
counter=val=0;
}
if (phase==1&&counter==(int)log2(notdone.size())+1){
tempval=val;
phase=2;
counter=val=0;
}
if (phase==2&&counter==9){
int best=notdone[tempval];
dist[best]=val+*max_element(dist.begin(), dist.end());
done.pb(best);
del[best]=1;
notdone.erase(find(notdone.begin(), notdone.end(), best));
phase=counter=val=0;
}
}
vector<int> Answer(){
return dist;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
namespace{
int counter=0, val=0, phase=0, tempval, dj=INT_MAX/2, best;
vector<int> dist, done, notdone;
vector<bool> del;
vector<deque<pii> > graph;
void sendover(){
if (notdone.empty())return;
dj=INT_MAX/2;
for (auto node:done){
while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
if (graph[node].empty())continue;
if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
}
for (int i=8; i>=0; --i)SendB((1<<i)&(dj-*max_element(dist.begin(), dist.end())));
}
}
void InitB(int n, int a, vector<int> u, vector<int> v, vector<int> c){
done.clear();
dist.clear();
graph.clear();
del.clear();
del.resize(n, 0);
done.resize(1, 0);
dist.resize(n, INT_MIN/2);
graph.resize(n);
dist[0]=counter=val=phase=0;
del[0]=1;
for (int i=1; i<n; ++i)notdone.pb(i);
for (int i=0; i<a; ++i){
graph[u[i]].pb(mp(c[i], v[i]));
graph[v[i]].pb(mp(c[i], u[i]));
}
for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
sendover();
}
void ReceiveB(bool x){
++counter;
val=val*2+x;
if (!phase){
if (val){
dist[best]=dj;
done.pb(best);
del[best]=1;
int id=0;
for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
notdone.erase(find(notdone.begin(), notdone.end(), best));
for (int i=log2(notdone.size()+1); i>=0; --i)SendB((1<<i)&id);
for (int i=8; i>=0; --i)SendB((1<<i)&(dj-*max_element(dist.begin(), dist.end())));
sendover();
}
else phase=1;
val=counter=0;
}
if (phase==1&&counter==(int)log2(notdone.size())+1){
tempval=val;
phase=2;
counter=val=0;
}
if (phase==2&&counter==9){
int best=notdone[tempval];
dist[best]=val+*max_element(dist.begin(), dist.end());
done.pb(best);
del[best]=1;
notdone.erase(find(notdone.begin(), notdone.end(), best));
phase=counter=val=0;
sendover();
}
}
