#include "Anthony.h"
#include <bitset>
#include <vector>
using namespace std;
using vi=vector<int>;
namespace {
const int maxn = int(2e4) + 10;
int n;
struct Edge { int l, r; } ev[maxn];
vector<int> es[maxn];
int lev[maxn];
int col[maxn];
void bfs() {
static int q[maxn];
static bitset<maxn> vis;
int f = 0, t = 1; vis.set(0);
while (f < t) {
int x = q[f++];
for (int ei : es[x]) {
int y = ev[ei].l + ev[ei].r - x;
if (vis[y]) continue;
vis.set(y);
lev[y] = lev[x]+1;
q[t++] = y;
}
}
}
void Read(int N, int M, vi &U, vi &V) {
n = N;
for (int i=0; i<M; ++i) {
ev[i] = {U[i], V[i]};
es[U[i]].push_back(i);
es[V[i]].push_back(i);
}
}
vi Case1(int N, int M, vi &U, vi &V) {
Read(N, M, U, V);
bfs();
for (int i=0; i<M; ++i) {
int a = ev[i].l, b = ev[i].r;
col[i] = min(lev[a], lev[b])%3;
}
return vi(col, col+M);
}
const int dict[6] = {0, 1, 1, 0, 0, 1};
void Go(int x, int p, int state) {
if (es[x].size() == 1u) return;
if (es[x].size() > 2u) {
int pc = dict[(state+5)%6];
for (int ei : es[x]) {
int y = ev[ei].l + ev[ei].r - x;
if (y == p) continue;
col[ei] = pc^1;
Go(y, x, pc^1);
}
return;
}
for (int ei : es[x]) {
int y = ev[ei].l + ev[ei].r - x;
if (y == p) continue;
col[ei] = dict[state];
Go(y, x, (state+1)%6);
}
}
vi Case2(int N, int M, vi &U, vi &V) {
Read(N, M, U, V);
for (int ei : es[0]) {
int y = ev[ei].l + ev[ei].r;
Go(y, 0, 1);
}
return vi(col, col+M);
}
} // namespace
namespace {
} // namespace
vi Mark(int N, int M, int A, int B, vi U, vi V) {
if (B == 0)
return Case1(N, M, U, V);
else
return Case2(N, M, U, V);
}
#include "Catherine.h"
#include <vector>
using namespace std;
using vi=vector<int>;
namespace {
int A, B;
int Move1(vi &y) {
int oc = 0;
for (int i=0; i<3; ++i) if (y[i]) ++oc;
if (oc == 1) for (int i=0; i<3; ++i) if (y[i]) return i;
int tmp = 0;
for (int i=0; i<3; ++i) if (y[i]) tmp += i;
tmp += 2;
tmp *= 2;
return tmp % 3;
}
} // namespace
namespace {
int last_move;
vector<int> hist;
bool know;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
last_move = -1;
}
int Move(vi y) {
if (B == 0) return Move1(y);
int last = last_move;
int which;
int ec = y[0] + y[1] + (last != -1);
if (know) {
if (ec >= 3) which = !last;
else which = !!y[1];
} else {
if (ec >= 3) {
which = (y[1]+(last==1) == 1);
if (which == last) which = -1;
know = true;
} else if (ec == 1) {
which = !!(y[1]+(last==1));
if (which == last) which = -1;
know = true;
} else {
if (last != -1) ++y[last];
int state = (y[0] == 2) ? 0 :
(y[1] == 2) ? 1 : 2;
if (last != -1) --y[last];
if (hist.size() == 3u) {
int t = hist[0]*1000 +
hist[1]*100 +
hist[2]*10 + state;
int down_sign = 212022212;
bool is_down = false;
for (int i=0; i<6; ++i) {
if (down_sign%10000 == t) { is_down = true; break; }
down_sign /= 10;
}
if (is_down) which = last_move;
else which = !!y[1];
know = true;
} else {
hist.push_back(state);
which = !!y[1];
}
}
}
if (which != -1) last_move = which;
return which;
}
