#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
static vector<int> edge[20000];
static int par[20000], pc[20000], ord[20000];
void dfs(int x, int p) {
par[x] = p;
ord[x] = -1;
if (!x) {
for (int i : edge[x]) pc[i] = 0, dfs(i, x);
}
else if (int(edge[x].size()) != 2) {
for (int i : edge[x]) {
if (i == p) continue;
pc[i] = pc[x] ^ 1;
dfs(i, x);
}
}
else {
ord[x] = ord[p] != -1 ? (ord[p] + 1) % 6 : (pc[x] ? 2 : 1);
for (int i : edge[x]) {
if (i == p) continue;
pc[i] = "010011"[ord[x]] - '0';
dfs(i, x);
}
}
}
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
for (int i = 0; i < m; ++i) {
edge[U[i]].push_back(V[i]);
edge[V[i]].push_back(U[i]);
}
if (A > 2) {
vector<int> dist(n, -1);
queue<int> q;
q.push(0);
dist[0] = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i : edge[x]) {
if (dist[i] != -1) continue;
q.push(i);
dist[i] = dist[x] + 1;
}
}
vector<int> ret(m);
for (int i = 0; i < m; ++i) {
int u = U[i], v = V[i];
if (dist[u] > dist[v]) swap(u, v);
ret[i] = dist[u] % 3;
}
return ret;
}
dfs(0, -1);
vector<int> ret(m);
for (int i = 0; i < m; ++i) {
int u = U[i], v = V[i];
if (u == par[v]) swap(u, v);
ret[i] = pc[u];
}
return ret;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
static int A, B, pr;
static vector<int> path;
void Init(int a, int b) {
A = a, B = b;
pr = -1;
path.clear();
}
int Move(vector<int> cnt) {
if (A > 2) {
int sum = 0;
for (int i : cnt) sum += i > 0;
if (sum == 1) {
for (int i = 0; ; ++i) if (cnt[i]) return i;
}
else if (sum == 2) {
for (int i = 0; ; ++i) if (!cnt[i]) return (i + 1) % 3;
}
else exit(1);
}
int deg = cnt[0] + cnt[1] + (pr != -1);
if (deg != 2) path.resize(6);
if (int(path.size()) > 5) {
if (deg != 2 && pr != -1) ++cnt[pr];
for (int i = 0; i < 2; ++i) {
if (cnt[i] == 1) {
if (deg == 2 || pr != i) return pr = i;
return -1;
}
}
exit(2);
}
while (cnt[0]--) path.push_back(0);
while (cnt[1]--) path.push_back(1);
if (int(path.size()) == 5) {
path.push_back(path.back());
for (int i = 0; i < 6; ++i) {
bool dif = 0;
for (int j = 0; j < 5; ++j) {
if (path[j] != "010011"[(i + j) % 6] - '0') dif = 1;
}
if (!dif) return -1;
}
}
return pr = path.back();
}
