#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int x,d;
edge(){}
edge(int _x,int _d)
{
x=_x;
d=_d;
}
bool operator<(const edge&e)const
{
return e.d<d;
}
};
int n;
vector<edge> v[2001];
int d[2001];
void dijkstra()
{
for(int i=0;i<n;i++)
d[i]=1e6;
priority_queue<edge> q;
q.push({0,0});
d[0]=0;
while(q.size())
{
edge t=q.top();
q.pop();
if(d[t.x]==t.d)
{
for(int i=0;i<v[t.x].size();i++)
{
edge nb=v[t.x][i];
if(d[nb.x]>nb.d+t.d)
{
d[nb.x]=nb.d+t.d;
q.push({nb.x,d[nb.x]});
}
}
}
}
}
int use[200001];
void sendshortest()
{
dijkstra();
int ver=-1;
for(int i=0;i<n;i++)
{
if(ver==-1&&!use[i]||ver!=-1&&d[ver]>d[i]&&!use[i])
ver=i;
}
//cout<<ver<<" ---- "<<d[ver]<<endl;
if(ver==-1)
{
Answer();
}
else
{
for(int i=0;i<10;i++)
if((1<<i)&ver)SendA(1);
else SendA(0);
for(int i=0;i<19;i++)
if((1<<i)&d[ver])SendA(1);
else SendA(0);
use[ver]=1;
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,std::vector<int> C)
{
n=N;
for(int i=0;i<U.size();i++)
{
v[U[i]].push_back({V[i],C[i]});
v[V[i]].push_back({U[i],C[i]});
}
sendshortest();
}
vector<bool> b;
void ReceiveA(bool x)
{
b.push_back(x);
if(b.size()==29)
{
int ver=0;
int dist=0;
for(int i=0;i<10;i++)
if(b[i])ver+=(1<<i);
for(int i=10;i<29;i++)
if(b[i])dist+=(1<<(i-10));
v[0].push_back({ver,dist});
sendshortest();
b.clear();
//cout<<ver<<" > "<<dist<<endl;
}
}
std::vector<int> Answer()
{
vector<int> ans;
for(int i=0;i<n;i++)
ans.push_back(d[i]);
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
struct edge1
{
int x,d;
edge1() {}
edge1(int _x,int _d)
{
x=_x;
d=_d;
}
bool operator<(const edge1&e)const
{
return e.d<d;
}
};
int n1;
vector<edge1> v1[2001];
int d1[2001];
void dijkstra1()
{
for(int i=0; i<n1; i++)
d1[i]=1e6;
priority_queue<edge1> q;
q.push({0,0});
d1[0]=0;
while(q.size())
{
edge1 t=q.top();
q.pop();
if(d1[t.x]==t.d)
{
for(int i=0; i<v1[t.x].size(); i++)
{
edge1 nb=v1[t.x][i];
if(d1[nb.x]>nb.d+t.d)
{
d1[nb.x]=nb.d+t.d;
q.push({nb.x,d1[nb.x]});
}
}
}
}
}
int use1[200001];
void sendshortest1()
{
dijkstra1();
int ver=-1;
for(int i=0; i<n1; i++)
{
if(ver==-1&&!use1[i]||ver!=-1&&d1[ver]>d1[i]&&!use1[i])
ver=i;
}
for(int i=0; i<10; i++)
if((1<<i)&ver)SendB(1);
else SendB(0);
for(int i=0; i<19; i++)
if((1<<i)&d1[ver])SendB(1);
else SendB(0);
use1[ver]=1;
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D)
{
n1=N;
for(int i=0;i<S.size();i++)
{
v1[S[i]].push_back({T[i],D[i]});
v1[T[i]].push_back({S[i],D[i]});
}
}
vector<bool> b1;
void ReceiveB(bool x)
{
b1.push_back(x);
if(b1.size()==29)
{
int ver=0;
int dist=0;
for(int i=0;i<10;i++)
if(b1[i])ver+=(1<<(i));
for(int i=10;i<29;i++)
if(b1[i])
{
//cout<<"! "<<i<<endl;
dist+=(1<<(i-10));
}
v1[0].push_back({ver,dist});
sendshortest1();
b1.clear();
//cout<<ver<<" < "<<dist<<endl;
}
}
