#include "Anthony.h"
#include <cstdlib>
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace A {
const int N = 20000;
const int zz[] = { 0, 1, 0, 0, 1, 1 };
int min(int a, int b) { return a < b ? a : b; }
int *ej[N], eo[N], dd[N], pp[N], cc_[N], qu[N], n;
void init(int n_) {
n = n_;
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
}
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
void bfs() {
for (int i = 0; i < n; i++)
dd[i] = n;
int cnt = 0;
dd[0] = 0, qu[cnt++] = 0;
for (int h = 0; h < cnt; h++) {
int i = qu[h], d = dd[i] + 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (dd[j] > d)
dd[j] = d, qu[cnt++] = j;
}
}
}
void dfs(int p, int i, int c) {
pp[i] = p;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
if (p == -1)
cc_[j] = 0, dfs(i, j, 0);
else if (eo[j] == 2)
cc_[j] = zz[(c + 1) % 6], dfs(i, j, (c + 1) % 6);
else
cc_[j] = zz[c % 6] ^ 1, dfs(i, j, zz[c % 6] ^ 1);
}
}
}
}
vi Mark(int n, int m, int a, int b, vi uu, vi vv) {
vi cc(m);
if (a >= 3 && b == 0) {
A::init(n);
for (int h = 0; h < m; h++)
A::append(uu[h], vv[h]), A::append(vv[h], uu[h]);
A::bfs();
for (int h = 0; h < m; h++)
cc[h] = A::min(A::dd[uu[h]], A::dd[vv[h]]) % 3;
} else {
A::init(n);
for (int h = 0; h < m; h++)
A::append(uu[h], vv[h]), A::append(vv[h], uu[h]);
A::dfs(-1, 0, -1);
for (int h = 0; h < m; h++) {
int i = A::pp[uu[h]] == vv[h] ? uu[h] : vv[h];
cc[h] = A::cc_[i];
}
}
return cc;
}
#include "Catherine.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace B {
const int zz[] = { 0, 1, 0, 0, 1, 1 };
int cc[6], h, c_;
}
void Init(int a, int b) {
a = b = a;
B::h = 0, B::c_ = -1;
}
int Move(vi kk) {
int a = kk.size();
if (a >= 3) {
for (int c = 0; c < 3; c++)
if (kk[(c + 2) % 3] == 0 && kk[c] != 0)
return c;
return -1;
} else {
int d = B::c_ != -1 ? 1 : 0;
for (int c = 0; c < 2; c++)
d += kk[c];
if (d == 1) {
B::h = -1;
for (int c = 0; c < 2; c++)
if (kk[c] != 0)
return B::c_ = c;
return -1;
} else if (d == 2) {
if (B::h == -1) {
for (int c = 0; c < 2; c++)
if (kk[c] != 0)
return B::c_ = c;
return -1;
} else {
for (int c = 0; c < 2; c++)
if (kk[c] != 0)
B::cc[B::h++] = c;
if (B::h < 5)
return B::c_ = B::cc[B::h - 1];
else {
for (int g = 0; g < 6; g++) {
int match = 1;
for (int h = 0; h < 5; h++)
if (B::zz[(g + h) % 6]) {
match = 0;
break;
}
if (match) {
B::h = -1;
return -1;
}
}
B::h = -1;
return B::c_ = B::cc[4];
}
}
} else {
B::h = -1;
return B::c_ == -1 ? (kk[0] == 1 ? 0 : 1) : kk[B::c_] == 0 ? -1 : (B::c_ ^= 1);
}
}
}
