#include "Anthony.h"
#include <vector>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
namespace {
} // namespace
vector<int> Mark(int N, int M, int A, int B,
vector<int> U, vector<int> V) {
vector<int> X(M, -1);
vector<vector<pii>> g(N, vector<pii>());
for (int i = 0; i < M; i++) {
int u = U[i], v = V[i];
g[u].push_back({v, i});
g[v].push_back({u, i});
}
vector<int> dist(N, N);
dist[0] = 0;
vector<int> q;
q.push_back(0);
for (int i = 0; i < (int)q.size(); i++) {
int v = q[i];
for (pii e : g[v]) if (dist[e.first] == N) {
dist[e.first] = dist[v] + 1;
q.push_back(e.first);
}
}
assert((int)q.size() == N);
if (A >= 3) {
for (int i = 0; i < M; i++)
X[i] = min(dist[U[i]], dist[V[i]]) % 3;
} else {
assert(M == N - 1);
vector<int> posInBamboo(N, -1);
for (int i = 0; i < N; i++) {
int v = q[i];
if (i == 0) {
for (auto [u, id] : g[v]) {
X[id] = 0;
}
continue;
}
int deg = (int)g[v].size();
if (deg == 1) continue;
int par = -1;
int parC = -1;
for (auto [u, id] : g[v]) if (dist[u] < dist[v]) {
par = u;
parC = X[id];
}
if (deg == 2) {
if (posInBamboo[par] != -1) {
posInBamboo[v] = (posInBamboo[par] + 1) % 6;
} else {
posInBamboo[v] = parC + 1;
}
int col = (posInBamboo[v] == 0 || posInBamboo[v] == 2 || posInBamboo[v] == 3 ? 0 : 1);
for (auto [u, id] : g[v]) if (u != par)
X[id] = col;
} else {
for (auto [u, id] : g[v]) if (u != par)
X[id] = parC ^ 1;
}
}
}
return X;
}
#include "Catherine.h"
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
namespace {
int A;
bool bambooPart;
vector<int> colors;
bool GoingUp(vector<int> s) {
vector<int> t = {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0};
reverse(t.begin(), t.end());
for (int i = 0; i + (int)s.size() <= (int)t.size(); i++) {
bool ok = true;
for (int j = 0; j < (int)s.size(); j++)
ok &= s[j] == t[i + j];
if (ok) return true;
}
return false;
}
} // namespace
void Init(int A, int B) {
::A = A;
::bambooPart = true;
::colors = vector<int>();
}
int Move(std::vector<int> y) {
if (::A > 2) {
int c = 0;
while(c < 3) {
if (y[c] > 0 && y[(c + 2) % 3] == 0) break;
c++;
}
assert(c < 3);
return c;
} else {
if (!::colors.empty()) y[::colors.back()]++;
int deg = y[0] + y[1];
int col = -2;
if (deg == 1) {
::bambooPart = false;
if (::colors.empty()) {
col = (y[0] > 0 ? 0 : 1);
} else {
col = -1;
}
} else if (deg == 2) {
if (!::bambooPart) {
assert(!::colors.empty());
y[::colors.back()]--;
col = (y[0] > 0 ? 0 : 1);
} else {
if ((int)::colors.size() < 3) {
if (!::colors.empty()) y[::colors.back()]--;
col = (y[0] > 0 ? 0 : 1);
} else {
y[::colors.back()]--;
col = (y[0] > 0 ? 0 : 1);
vector<int> s = ::colors;
s.push_back(col);
if (!::GoingUp(s)) col = -1;
::bambooPart = false;
}
}
} else {
assert(deg > 2);
::bambooPart = false;
col = (y[0] == 1 ? 0 : 1);
assert(y[col] == 1);
if (!::colors.empty() && ::colors.back() == col) col = -1;
}
if (col == -1) {
int x = ::colors.back();
::colors.push_back(x);
} else {
::colors.push_back(col);
}
return col;
}
}
