#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
vector<vector<int>> adj;
vector<int> dist;
void bfs() {
queue<int> q;
dist.resize(adj.size(), INT_MAX);
q.push(0);
dist[0] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto u : adj[v]) {
if (dist[u] > dist[v] + 1) {
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
}
vector<int> s{0, 0, 1, 0, 1, 1};
vector<pair<int, int>> v;
void dfs(int ver, int par, int col, int len) {
v[ver] = {par, col};
int numchild = adj[ver].size() - (par != -1);
if (numchild > 1) {
for (auto c : adj[ver]) if (c != par) {
dfs(c, ver, !col, -1);
}
} else {
if (len == -1) {
if (col == 0) len = 1;
else len = 3;
}
for (auto c : adj[ver]) if (c != par) {
dfs(c, ver, s[len], (len + 1) % 6);
}
}
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
adj.resize(N);
for (int i = 0; i < M; ++i) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
if (A >= 3) {
bfs();
vector<int> ret(M);
for (int i = 0; i < M; ++i) {
ret[i] = min(dist[U[i]], dist[V[i]]) % 3;
}
return ret;
}
v.resize(N);
dfs(0, -1, 0, -1);
vector<int> ret(M);
for (int i = 0; i < M; ++i) {
if (v[U[i]].first == V[i]) {
ret[i] = v[U[i]].second;
} else {
ret[i] = v[V[i]].second;
}
}
return ret;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B;
int prv;
vector<int> pat{0, 0, 1, 0, 1, 1};
vector<int> cur;
bool correct;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
::prv = -1;
::correct = false;
}
int Move(std::vector<int> y) {
if (A >= 3) {
if (y[0] == 0) {
if (y[1] == 0) return 2;
return 1;
} else if (y[1] == 0) {
if (y[2] == 0) return 0;
return 2;
} else if (y[2] == 0) {
if (y[0] == 0) return 1;
return 0;
}
assert(false);
}
int cntadj = accumulate(begin(y), end(y), 0) + (prv != -1);
if (cntadj > 2) {
correct = true;
if (prv != -1 && y[prv] == 0) return -1;
if (y[0] == 1) return prv = 0;
else if (y[1] == 1) return prv = 1;
assert(false);
}
if (cntadj == 1) {
correct = true;
if (prv != -1) {
return -1;
} else {
if (y[0] == 1) return prv = 0;
else if (y[1] == 1) return prv = 1;
assert(false);
}
}
if (correct) {
if (y[0] > 0) return prv = 0;
else if (y[1] > 0) return prv = 1;
assert(false);
}
if (prv == -1) {
if (y[0] > 0) {
cur.push_back(0);
if (y[1] > 0) {
cur.push_back(1);
return prv = 1;
} else {
cur.push_back(0);
return prv = 0;
}
} else {
assert(y[1] > 0);
cur.push_back(1);
cur.push_back(1);
return prv = 1;
}
} else {
if (y[0] > 0) {
cur.push_back(0);
} else {
assert(y[1] > 0);
cur.push_back(1);
}
if (cur.size() == 5) {
for (int i = 0; i < 10; ++i) {
bool g = true;
for (int j = 0; j < 5; ++j) {
if (cur[j] != pat[(j + i) % size(pat)]) g = false;
}
if (g) {
correct = true;
return -1;
}
}
correct = true;
assert(y[cur.back()] > 0);
return prv = cur.back();
} else {
assert(y[cur.back()] > 0);
return prv = cur.back();
}
}
}
