#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
#define st first
#define nd second
int odl=0,numer=0;
int k1=0,k2=0;
int n;
int p=0;
bool r1=false,r2=false;
int teraz=0;
vector<int>w(2000,-1);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
vector<vector<pair<int,int>>>graf;
int ile=1;
void wyslij(int x,int k)
{
//cout<<x<<" A"<<endl;
for(int i=0;i<k;i++)
{
SendA(x&(1<<i));
}
}
vector<int>Answer()
{
vector<int>v(n);
for(int i=0;i<n;i++)
{
v[i]=w[i];
}
return v;
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C)
{
n=N;
w[0]=0;
for(int i=0;i<n;i++)
{
graf.push_back({{}});
}
for(int i=0;i<A;i++)
{
graf[U[i]].push_back({C[i],V[i]});
graf[V[i]].push_back({C[i],U[i]});
}
for(long unsigned int i=1;i<graf[0].size();i++)
{
q.push({graf[0][i].st,graf[0][i].nd});
}
q.push({1048575,0});
if(ile<n)
{
for(int i=0;i<9;i++)
{
SendA(q.top().st&(1<<i));
}
}
}
void ReceiveA(bool x)
{ //cout<<k2<<" "<<k1<<endl;
while(w[q.top().nd]>-1 && q.size()>1)
{
q.pop();
}
if(teraz==0)
{
if(r1==false)
{
r1=true;
k1=0;
odl=0;
}
if(x)
{
odl+=pow(2,k1);
}
k1++;
if(k1==9)
{
//cout<<"A"<<endl;
if(q.top().st-p>odl or q.size()==1)
{
numer=0;k2=0;
teraz=1;
}
else
{
odl=q.top().st-p;
w[q.top().nd]=odl+p;
ile++;
for(long unsigned int i=1;i<graf[q.top().nd].size();i++)
{
q.push({graf[q.top().nd][i].st+w[q.top().nd],graf[q.top().nd][i].nd});
}
p+=odl;
odl=0;numer=0;k1=0;k2=0;
teraz=2;
// cout<<q.top().nd<<endl;
wyslij(q.top().nd,11);
}
r1=false;
return;
}
}
if(teraz==1)
{
if(r2==false)
{
r2=true;
k2=0;
numer=0;
//cout<<"AAAAAAAA"<<endl;
}
if(x)
{
numer+=pow(2,k2);
}
k2++;
//cout<<numer<<endl;
if(k2==11)
{//cout<<"AA"<<endl;
ile++;
w[numer]=odl+p;
for(long unsigned int i=1;i<graf[numer].size();i++)
{
q.push({graf[numer][i].st+w[numer],graf[numer][i].nd});
}
while(w[q.top().nd]>-1 && q.size()>1)
{
q.pop();
}
p+=odl;
teraz=0;
odl=0;numer=0;k1=0;k2=0;
if(ile<n)
{
if(q.size()==1)
{
wyslij(q.top().st,9);
}
else
{
wyslij(q.top().st-p,9);
}
}
r2=false;
return;
}
}
if(teraz==2)
{
if(r1==false)
{
r1=true;
k1=0;
odl=0;
//cout<<"QQQQ"<<endl;
}
if(x)
{
odl+=pow(2,k1);
}
k1++;
if(k1==9)
{//cout<<"AAA"<<endl;
if(q.top().st-p<odl && q.size()>1)
{
odl=q.top().st-p;
w[q.top().nd]=odl+p;
ile++;
for(long unsigned int i=1;i<graf[q.top().nd].size();i++)
{
q.push({graf[q.top().nd][i].st+w[q.top().nd],graf[q.top().nd][i].nd});
}
if(q.size()>1)
{
wyslij(q.top().st-p,9);
}
else
{
wyslij(q.top().st,9);
}
// cout<<q.top().nd<<endl;
wyslij(q.top().nd,11);
p+=odl;
odl=0;numer=0;k1=0;k2=0;
}
else
{
k2=0;numer=0;k1=0;
teraz=1;
wyslij(odl,9);
}
r1=false;
return;
}
}
}
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
#define st first
#define nd second
int odl_b=0,numer_b=0;
int k1_b=0,k2_b=0;
bool r1_b,r2_b;
int n_b;
int p_b=0;
int teraz_b=2;
int ile_b=1;
vector<int>w_b(2000,-1);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q_b;
vector<vector<pair<int,int>>>graf_b;
void wyslij_b(int x,int k)
{
//cout<<x<<" B"<<endl;
for(int i=0;i<k;i++)
{
SendB(x&(1<<i));
}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D)
{
w_b[0]=0;
n_b=N;
for(int i=0;i<n_b;i++)
{
graf_b.push_back({{}});
}
for(int i=0;i<B;i++)
{
graf_b[S[i]].push_back({D[i],T[i]});
graf_b[T[i]].push_back({D[i],S[i]});
}
for(long unsigned int i=1;i<graf_b[0].size();i++)
{
q_b.push({graf_b[0][i].st,graf_b[0][i].nd});
}
q_b.push({1048575,0});
}
void ReceiveB(bool x)
{
while(w_b[q_b.top().nd]>-1 && q_b.size()>1)
{
q_b.pop();
}
if(teraz_b==0)
{
if(r1_b==false)
{
r1_b=true;
k1_b=0;
odl_b=0;
}
if(x)
{
odl_b+=pow(2,k1_b);
}
k1_b++;
if(k1_b==9)
{
if(q_b.top().st-p_b>odl_b or q_b.size()==1)
{
teraz_b=1;
}
else
{
odl_b=q_b.top().st-p_b;
w_b[q_b.top().nd]=odl_b+p_b;
ile_b++;
for(long unsigned int i=1;i<graf_b[q_b.top().nd].size();i++)
{
q_b.push({graf_b[q_b.top().nd][i].st+w_b[q_b.top().nd],graf_b[q_b.top().nd][i].nd});
}
p_b+=odl_b;
odl_b=0;numer_b=0;k1_b=0;k2_b=0;
teraz_b=2;
wyslij_b(q_b.top().nd,11);
}
k1_b=false;
return;
}
}
if(teraz_b==1)
{
if(r2_b==false)
{
r2_b=true;
k2_b=0;
numer_b=0;
}//cout<<k2_b<<endl;
if(x)
{
numer_b+=pow(2,k2_b);
}//cout<<numer_b<<endl;
k2_b++;
if(k2_b==11)
{//cout<<"BB"<<endl;
w_b[numer_b]=odl_b+p_b;
ile_b++;
for(long unsigned int i=1;i<graf_b[numer_b].size();i++)
{
q_b.push({graf_b[numer_b][i].st+w_b[numer_b],graf_b[numer_b][i].nd});
}
while(w_b[q_b.top().nd]>-1 && q_b.size()>1)
{
q_b.pop();
}
p_b+=odl_b;
teraz_b=0;
odl_b=0;numer_b=0;k1_b=0;k2_b=0;
if(ile_b<n_b)
{
if(q_b.size()==1)
{
wyslij_b(q_b.top().st,9);
}
else
{
wyslij_b(q_b.top().st-p_b,9);
}
}
r2_b=false;
return;
}
}
if(teraz_b==2)
{
if(r1_b==false)
{
r1_b=true;
k1_b=0;
odl_b=0;
}
if(x)
{
odl_b+=pow(2,k1_b);
}
k1_b++;
if(k1_b==9)
{//cout<<"BBB"<<endl;
if(q_b.top().st-p_b<odl_b && q_b.size()>1)
{
odl_b=q_b.top().st-p_b;
w_b[q_b.top().nd]=odl_b+p_b;
ile_b++;
for(long unsigned int i=1;i<graf_b[q_b.top().nd].size();i++)
{
q_b.push({graf_b[q_b.top().nd][i].st+w_b[q_b.top().nd],graf_b[q_b.top().nd][i].nd});
}
wyslij_b(q_b.top().st-p_b,9);
wyslij_b(q_b.top().nd,11);
p_b+=odl_b;
odl_b=0;numer_b=0;k1_b=0;k2_b=0;
}
else
{
teraz_b=1;
if(q_b.size()==1)
{
wyslij_b(q_b.top().st,9);
}
else
{
wyslij_b(q_b.top().st-p_b,9);
}
}
r1_b=false;
return;
}
}
}
