#include "Anthony.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#define N_ 20100
using namespace std;
vector<int>E[N_];
int Q[N_], D[N_], w[6] = { 0,0,1,1,0,1 }, T[N_], Dep[N_], Col[N_], BB;
void DFS(int a, int pp) {
int c = E[a].size();
if (a)c--;
if (c >= 2)T[a] = 0;
for (auto &x : E[a]) {
if (x == pp)continue;
T[x] = T[a] + 1;
if (a == 0) {
Col[x] = 1;
}
else {
if (T[a] == 0)Col[x] = !Col[a];
else Col[x] = w[(T[a] - 1) % 6];
}
Dep[x] = Dep[a] + 1;
DFS(x, a);
}
}
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
std::vector<int> X(M);
int i;
BB = B;
for (i = 0; i < M; i++) {
E[U[i]].push_back(V[i]);
E[V[i]].push_back(U[i]);
}
Dep[0] = 0;
if (BB) {
DFS(0, 0);
for (i = 0; i < M; i++) {
if (Dep[U[i]] < Dep[V[i]])X[i] = Col[V[i]];
else X[i] = Col[U[i]];
}
}
else {
int head = 0, tail = 0;
Q[++tail] = 0;
for (i = 0; i <= N; i++)D[i] = 1e9;
D[0] = 0;
while (head < tail) {
int x = Q[++head];
for (auto &t : E[x]) {
if (D[t] > D[x] + 1) {
D[t] = D[x] + 1;
Q[++tail] = t;
}
}
}
for (i = 0; i < M; i++) {
X[i] = min(D[U[i]], D[V[i]]) % 3;
}
}
return X;
}
#include "Catherine.h"
#include <vector>
int s, ok, dd, BBB;
int L[3];
void Init(int A, int B) {
BBB = B;
s = 0; L[0] = L[1] = L[2] = -1;
ok = 0;
dd = 0;
}
void Put(int a) {
L[2] = L[1];
L[1] = L[0];
L[0] = a;
s++;
}
int Move(std::vector<int> y) {
int i;
if (BBB == 0) {
if (!y[0]) {
if (!y[1])return 2;
return 1;
}
if (!y[1]) {
if (!y[2])return 0;
return 2;
}
if (!y[2]) {
if (!y[0])return 1;
return 0;
}
}
if (ok) {
int x;
if (!y[0]) x = 1;
else if (!y[1]) x = 0;
else x = !L[0];
Put(x);
return x;
}
if (!s) {
if (y[0] + y[1] >= 3) {
ok = 1;
if (y[0] == 1) {
Put(0); return 0;
}
if (y[1] == 1) {
Put(1); return 1;
}
}
if (y[0] + y[1] == 1) {
ok = 1;
if (y[0]) {
Put(0); return 0;
}
else {
Put(1); return 1;
}
}
if (y[1] == 2 || y[0] == 2)dd = 1;
if (y[1]) {
Put(1);
return 1;
}
Put(0);
return 0;
}
if (y[0] + y[1] >= 2) {
ok = 1;
if (!y[L[0]]) {
Put(L[0]);
return -1;
}
int x = !L[0];
Put(x);
return x;
}
if (y[0] + y[1] == 0) {
ok = 1;
Put(L[0]);
return -1;
}
int cur = 0;
if (y[0])cur = 0;
else cur = 1;
if (s < 2) {
Put(cur);
return cur;
}
if (s == 2) {
if (dd) {
ok = 1;
if (L[1] == 0 && L[0] == 0) {
Put(L[0]);
return -1;
}
if (L[1] == 0) {
if (cur == 0) {
Put(cur); return cur;
}
else {
Put(L[0]); return -1;
}
}
else {
if (cur == 0) {
Put(cur); return cur;
}
else {
Put(L[0]); return -1;
}
}
}
if (L[0] == 0) {
ok = 1;
if (cur == 1) {
Put(cur); return cur;
}
else {
Put(L[0]); return -1;
}
}
Put(cur); return cur;
}
if (s == 3) {
ok = 1;
if (cur == 0) {
Put(cur); return cur;
}
else {
Put(L[0]); return -1;
}
}
}
