#include "Azer.h"
#include <vector>
#include <iostream>
#include <queue>
#include <array>
#define ll long long
using namespace std;
namespace{
ll n, distA[2000], pwa = 0, cura = 0, sza = 0, wa = 0, va = 0, tota;
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pqA;
vector <array<ll, 2>> adjA[2000];
void sendWeightA(ll u) {
for (int j=8; j>=0; --j) {
if (u & (1LL<<j)) SendA(1);
else SendA(0);
}
}
void sendNodeA(ll u) {
for (int j=10; j>=0; --j) {
if (u & (1LL<<j)) SendA(1);
else SendA(0);
}
}
void nxA() {
while (!pqA.empty()) {
auto [w, u] = pqA.top();
if (distA[u] != w) pqA.pop();
else break;
}
if (!pqA.empty()) {
auto [w, u] = pqA.top();
wa = w-pwa, va = u;
sendWeightA(w-pwa);
}
else {
wa = (1LL<<9)-1;
sendWeightA((1LL<<9)-1);
}
}
void propB(ll u, ll w) {
--tota;
distA[u] = w;
for (auto [v, x] : adjA[u]) {
if (distA[v] > w+x) {
distA[v] = w+x;
pqA.push({w+x, v});
}
}
if (tota) nxA();
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
pwa = cura = sza = wa = va = 0, tota = N-1, n = N;
for (int i=0; i<N; ++i) {
distA[i] = 1e18;
adjA[i].clear();
}
for (int i=0; i<A; ++i) {
adjA[U[i]].push_back({V[i], C[i]});
adjA[V[i]].push_back({U[i], C[i]});
}
distA[0] = 0;
for (auto [v, x] : adjA[0]) {
if (distA[v] > x) {
distA[v] = x;
pqA.push({x, v});
}
}
nxA();
}
void ReceiveA(bool x) {
++sza;
cura *= 2, cura += (ll)x;
if (sza == 9) {
//cout << 'A' << " " << cura << " " << wa << endl;
if (cura >= wa) {
sendNodeA(va);
sza = 0;
pwa = wa = wa + pwa;
pqA.pop();
propB(va, wa);
}
else pwa = wa = cura + pwa;
cura = 0;
}
else if (sza == 20) {
va = cura;
propB(va, wa);
sza = cura = 0;
}
}
std::vector<int> Answer() {
vector <int> F;
for (int i=0; i<n; ++i) F.push_back(distA[i]);
return F;
}
#include "Baijan.h"
#include <vector>
#include <iostream>
#include <queue>
#include <array>
#define ll long long
using namespace std;
namespace{
ll distB[2000], pwb = 0, curb = 0, szb = 0, wb = 0, vb = 0, totb;
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pqB;
vector <array<ll, 2>> adjB[2000];
void sendWeightB(ll u) {
for (int j=8; j>=0; --j) {
if (u & (1LL<<j)) SendB(1);
else SendB(0);
}
}
void sendNodeB(ll u) {
for (int j=10; j>=0; --j) {
if (u & (1LL<<j)) SendB(1);
else SendB(0);
}
}
void nxB() {
while (!pqB.empty()) {
auto [w, u] = pqB.top();
if (distB[u] != w) pqB.pop();
else break;
}
if (!pqB.empty()) {
auto [w, u] = pqB.top();
wb = w-pwb, vb = u;
sendWeightB(w-pwb);
}
else {
wb = (1LL<<9)-1;
sendWeightB((1LL<<9)-1);
}
}
void propB(ll u, ll w) {
--totb;
distB[u] = w;
for (auto [v, x] : adjB[u]) {
if (distB[v] > w+x) {
distB[v] = w+x;
pqB.push({w+x, v});
}
}
if (totb) nxB();
}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
pwb = curb = szb = wb = vb = 0, totb = N-1;
for (int i=0; i<N; ++i) {
distB[i] = 1e18;
adjB[i].clear();
}
for (int i=0; i<B; ++i) {
adjB[S[i]].push_back({T[i], D[i]});
adjB[T[i]].push_back({S[i], D[i]});
}
distB[0] = 0;
for (auto [v, x] : adjB[0]) {
if (distB[v] > x) {
distB[v] = x;
pqB.push({x, v});
}
}
nxB();
}
void ReceiveB(bool y) {
++szb;
curb *= 2, curb += (ll)y;
if (szb == 9) {
//cout << 'B' << " " << curb << " " << wb << endl;
if (curb > wb) {
sendNodeB(vb);
szb = 0;
pwb = wb = wb + pwb;
pqB.pop();
propB(vb, wb);
}
else pwb = wb = curb + pwb;
curb = 0;
}
else if (szb == 20) {
vb = curb;
propB(vb, wb);
szb = curb = 0;
}
}
