#include "Anthony.h"
#include <queue>
#include <utility>
#include <vector>
namespace {
using std::vector;
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
vector<vector<int>> G(N);
for (int i = 0; i < M; ++i) {
G[U[i]].push_back(i);
G[V[i]].push_back(i);
}
std::queue<int> que;
vector<int> dist(N, N);
vector<int> colors(N, -1);
dist[0] = 0;
que.push(0);
for (; !que.empty(); ) {
const int u = que.front();
que.pop();
for (const int i : G[u]) {
const int v = U[i] ^ V[i] ^ u;
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
que.push(v);
if (A == 2) {
if (u == 0) {
colors[v] = 0;
} else if (G[u].size() >= 3) {
colors[v] = ("010011"[colors[u]] == '0') ? 1 : 0;
} else {
colors[v] = (colors[u] + 1) % 6;
}
}
}
}
}
vector<int> x(M, -1);
for (int i = 0; i < M; ++i) {
int u = U[i], v = V[i];
if (dist[u] > dist[v]) {
std::swap(u, v);
}
if (A == 2) {
x[i] = "010011"[colors[v]] - '0';
} else {
x[i] = dist[u] % 3;
}
}
return x;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B, e = -1;
bool ok = false;
vector<int> adj;
vector<int> code{0, 1, 0, 0, 1, 1};
bool extendable(vector<int> a) {
for (int i = 0; i < size(code); ++i) {
bool yay = true;
for (int k = 0; k < size(a); ++k) {
if (a[k] != code[(i + k) % size(code)]) {
yay = false;
break;
}
}
if (yay) {
return true;
}
}
return false;
}
}
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(std::vector<int> yy) {
vector<int> y = yy;
if (e != -1) {
y[e] += 1;
}
int deg = accumulate(y.begin(), y.end(), 0);
if (A >= 3) {
int fi = -1, se = -1, cnt = 0;
for (int i = 0; i < A; ++i) {
if (y[i]) {
fi = fi == -1 ? i : fi;
se = i;
cnt += 1;
}
}
if (fi != 0 || se != 2) {
return e = fi;
} else {
return e = se;
}
} else {
if (deg == 2) {
if (ok) {
return e = find(yy.begin(), yy.end(), 1) - yy.begin();
}
int a = -1, b = -1;
for (int i = 0; i < A; ++i) {
if (y[i]) {
a = a == -1 ? i : a;
b = i;
}
}
if (e == -1) {
adj.push_back(a);
adj.push_back(b);
return e = b;
}
int c = a ^ b ^ e;
adj.push_back(c);
if (adj.size() == 5) {
ok = true;
if (extendable(adj)) {
return -1;
}
return c;
} else {
return e = c;
}
} else {
ok = true;
int ans = find(y.begin(), y.end(), 1) - y.begin();
if (ans == e) {
return -1;
} else {
return e = ans;
}
}
assert(false);
}
}
