#include <bits/stdc++.h>
#include "Anthony.h"
using namespace std;
namespace {
} // namespace
std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
vector<int> rt (M, 0);
vector<vector<int>> G (N);
for (int i = 0; i < M; i++) {
G[U[i]].push_back(V[i]);
G[V[i]].push_back(U[i]);
}
if (A >= 3) {
vector<int> dep (N, -1);
queue<int> Q;
Q.push(0);
dep[0] = 0;
while (!Q.empty()) {
int p = Q.front();
Q.pop();
for (auto e : G[p]) {
if (dep[e] == -1) {
dep[e] = dep[p] + 1;
Q.push(e);
}
}
}
for (int i = 0; i < M; i++) {
int x = U[i], y = V[i];
if (dep[x] > dep[y]) {
swap(x, y);
}
rt[i] = dep[x] % 3;
}
} else {
vector<int> col (N, 0);
vector<int> dep (N, 0);
function<void(int, int, int)> dfs = [&] (int p, int fa, int cdis) {
static char str[] = "110100";
if (p) {
cdis = (G[fa].size() == 2u) ? (cdis % 6 + 1) : (0);
col[p] = (!cdis) ? (col[fa] ^ 1) : (str[cdis - 1] - '0');
dep[p] = dep[fa] + 1;
}
for (auto e : G[p]) {
if (e ^ fa) {
dfs(e, p, cdis);
}
}
};
dfs(0, -1, 0);
for (int i = 0; i < M; i++) {
int x = U[i], y = V[i];
if (dep[x] > dep[y]) {
swap(x, y);
}
rt[i] = col[y];
// cerr << x << " " << y << " " << rt[i] << '\n';
}
}
return rt;
}
#include <bits/stdc++.h>
#include "Catherine.h"
using namespace std;
namespace {
int A, B;
bool has_dir;
int last_col;
vector<int> seq;
bool match(const char* s) {
int len = strlen(s);
if (len > seq.size()) {
return false;
}
int t = seq.size();
while (len-- && t--) {
if (s[len] - '0' != seq[t]) {
return false;
}
}
return true;
}
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
has_dir = false;
last_col = -1;
}
int Move(std::vector<int> y) {
if (A >= 3) {
const static int go[3] = {1, 2, 0};
vector<int> id;
for (int i = 0; i < A; i++) {
if (y[i]) {
id.push_back(i);
}
}
int sz = id.size();
assert(sz <= 2 && sz >= 1);
if (sz == 1) {
return id[0];
} else {
return go[3 ^ id[0] ^ id[1]];
}
} else {
if (has_dir) {
if (!y[0] + !y[1] == 1) {
return last_col = !y[0];
} else {
return last_col = last_col ^ 1;
}
} else {
int sum = last_col != -1;
for (auto x : y) {
sum += x;
}
if (sum > 2) {
has_dir = true;
if (last_col == -1) {
return last_col = y[0] > y[1];
} else {
if (!y[last_col]) {
return -1;
} else {
return last_col = last_col ^ 1;
}
}
} else if (sum == 1) {
has_dir = true;
if (last_col == -1) {
return last_col = !y[0];
} else {
return -1;
}
} else {
if (last_col == -1) {
if (y[0] == 2) {
last_col = 0;
seq = vector<int>{0, 0};
} else if (y[1] == 2) {
last_col = 1;
seq = vector<int>{1, 1};
} else {
last_col = 1;
seq = vector<int>{0, 1};
}
return last_col;
} else {
seq.push_back(!y[0]);
int sz = seq.size();
if (sz >= 4) {
if (seq[sz - 2] == 1 && seq[sz - 3] == 0 && seq[sz - 4] == 1) {
has_dir = true;
if (seq[sz - 1] == 0) {
return -1;
}
} else if (seq[sz - 1] == 1 && seq[sz - 2] == 0 && seq[sz - 3] == 1) {
has_dir = true;
if (seq[sz - 4] == 1) {
return -1;
}
} else if (match("00110") || match("01001")) {
has_dir = true;
return -1;
}
}
return last_col = !y[0];
}
}
}
}
return -1;
}
