#include "Azer.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
static const int N = 2007, mxc = (1 << 9)-1, inf = 1e9;
static int n, m, ldis, str, x, y, w;
static set <pii> s;
static vector <pii> adj[N];
static vector <int> d;
static queue <int> bits;
void InitA(int nn, int aa, vector<int> uu, vector<int> vv, vector<int> cc) {
n = nn; m = aa;
for (int i = 0; i < m; i++) {
adj[uu[i]].pb({vv[i], cc[i]});
adj[vv[i]].pb({uu[i], cc[i]});
}
str = -1;
d.resize(n, inf);
d[0] = 0;
for (auto it : adj[0]) d[it.F] = it.S;
for (int i = 1; i < n; i++) s.insert({d[i], i});
}
void ReceiveA(bool bit) {
if (str != -1) bits.push(bit);
else str = 0;
auto snum = [&](int xx, int si) {
for (int i = 0; i < si; i++) SendA((xx>>i)&1);
};
auto rnum = [&](int si) {
int xx = 0;
for (int i = 0; i < si; i++) {
xx |= (int)bits.front() << i;
bits.pop();
}
return xx;
};
if (str == 1 && bits.size() < 9) return;
if (str == 2 && bits.size() < 11) return;
if (!str) {
y = n, w = mxc;
for (auto it : s) {
if (it.F-ldis < w) {
w = it.F-ldis;
y = it.S;
}
}
snum(w, 9);
// cout << "A sends " << w << "\n";
str = 1;
return;
}
else if (str == 1) {
x = rnum(9);
// cout << "A recieves " << x << "\n";
if (x > w) snum(y, 11);//, cout << "A sends " << y << "\n";
else {
str = 2;
return;
}
}
else {
y = rnum(11);
w = x;
// cout << "A recievese " << y << "\n";
}
// cout << d[y] << " " << ldis << " " << w << "\n";
assert(s.find({d[y], y}) != s.end());
s.erase({d[y], y});
d[y] = (ldis += w);
for (auto it : adj[y]) {
if (d[y]+it.S < d[it.F]) {
assert(s.find({d[it.F], it.F}) != s.end());
s.erase({d[it.F], it.F});
d[it.F] = d[y]+it.S;
s.insert({d[it.F], it.F});
}
}
str = -1;
// cout << ldis << "\n";
// for (auto it : d) cout << it << " "; cout << "\n";
}
vector<int> Answer() {
return d;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
static const int N = 2007, mxc = (1 << 9)-1, inf = 1e9;
static int n, m, ldis, str, x, y, w, ncnt;
static set <pii> s;
static vector <pii> adj[N];
static vector <int> d;
static queue <int> bits;
void InitB(int nn, int bb, vector<int> ss, vector<int> tt, vector<int> dd) {
n = nn; m = bb;
for (int i = 0; i < m; i++) {
adj[ss[i]].pb({tt[i], dd[i]});
adj[tt[i]].pb({ss[i], dd[i]});
}
d.resize(n, inf);
d[0] = 0;
for (auto it : adj[0]) d[it.F] = it.S;
for (int i = 1; i < n; i++) s.insert({d[i], i});
str = 0;
ncnt = n-1;
if (n > 1) SendB(1);
}
void ReceiveB(bool bit) {
bits.push(bit);
// cout << "B" << bit << "\n";
auto snum = [&](int xx, int si) {
for (int i = 0; i < si; i++) SendB((xx>>i)&1);
};
auto rnum = [&](int si) {
int xx = 0;
for (int i = 0; i < si; i++) {
xx |= (int)bits.front() << i;
bits.pop();
}
return xx;
};
if (!str && bits.size() < 9) return;
if (str && bits.size() < 11) return;
if (!str) {
y = n, w = mxc;
for (auto it : s) {
if (it.F-ldis < w) {
w = it.F-ldis;
y = it.S;
}
}
x = rnum(9);
// cout << "B recieves " << x << "\n";
if (x >= w) {
snum(w, 9);
snum(y, 11);
// cout << "B sends " << w << " " << y << "\n";
}
else {
snum(w, 9);
// cout << "B sends " << w << "\n";
str = 1;
return;
}
}
else {
y = rnum(11);
w = x;
// cout << "B recieves " << y << "\n";
}
assert(s.find({d[y], y}) != s.end());
s.erase({d[y], y});
d[y] = (ldis += w);
for (auto it : adj[y]) {
if (d[y]+it.S < d[it.F]) {
assert(s.find({d[it.F], it.F}) != s.end());
s.erase({d[it.F], it.F});
d[it.F] = d[y]+it.S;
s.insert({d[it.F], it.F});
}
}
ncnt--;
if (ncnt) SendB(1);
str = 0;
}
