#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
vector <pair<int, int>> adj[20005];
vector <int> X, path = {0, 1, 1, 0, 1, 0}, dist;
} // namespace
void dfs(int idx, int par, int z, int lst) {
for (auto [i, j] : adj[idx]) {
if (i != par) {
dist[i] = dist[idx]+1;
if (adj[idx].size()>2) {
X[j] = lst^1;
dfs(i, idx, -1, X[j]);
}
else {
if (z == -1) z = !lst;
X[j] = path[z];
dfs(i, idx, (z+1)%6, X[j]);
}
}
}
}
vector <int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
for (int i=0; i<M; i++) {
adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
}
X.resize(M);
dist.resize(N);
dfs(0, -1, -1, 0);
return X;
}
/*
*/
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace {
int A, B;
int lst = -1, z = -1;
vector <ll> v;
vector <int> path = {0, 1, 1, 0, 1, 0};
vector <bool> ok(16);
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
for (int i=1; i<6; i++) {
if (i == 4) continue;
ll z = 0;
for (int j=0; j<4; j++) {
ll idx = (i+j)%6;
z += path[idx]*(1LL<<j);
}
ok[z] = 1;
}
lst = -1, z = -1;
v.clear();
}
int Move(vector<int> y) {
if (!y[0] && !y[1]) {
z = lst;
return -1;
}
if (z != -1) {
if (!y[0]) {
z = 1;
return z;
}
if (!y[1]) {
z = 0;
return z;
}
z ^= 1;
return z;
}
ll adj = (lst != -1);
for (int i=0; i<A; i++) {
adj += y[i];
}
if (adj != 2) {
if (lst != -1) y[lst]++;
if (y[1]<y[0]) {
z = 1;
if (lst == 1) return -1;
return 1;
}
else {
z = 0;
if (lst == 0) return -1;
return 0;
}
return z;
}
if (!y[0]) lst = 1;
else lst = 0;
v.push_back(lst);
if (v.size() == 5) {
ll a = 0, b = 0;
z = lst;
for (int i=0; i<4; i++) a += (1LL<<i)*v[i];
for (int i=1; i<5; i++) b += (1LL<<i)*v[i];
if (!ok[a] && !ok[b]) return -1;
return lst;
}
return lst;
}
