#include <bits/stdc++.h>
#include "Anthony.h"
using namespace std;
namespace {
const int N_MAX = 20000;
const int pattern[] = {0, 1, 0, 0, 1, 1};
int N, M, A, B;
int edge_u[N_MAX], edge_v[N_MAX];
vector <int> adj[N_MAX];
int other (int i, int u) {
return (u != edge_v[i] ? edge_v[i] : edge_u[i]);
}
int up_edge[N_MAX];
int color[N_MAX + 1];
int chain[N_MAX];
void dfs () {
fill(up_edge, up_edge + N, -1);
up_edge[0] = M; color[M] = 1 - N % 2;
chain[0] = -1;
queue <int> q;
q.push(0);
while (q.empty() == false) {
int u = q.front();
q.pop();
if ((int) adj[u].size() == 2 && u != 0) {
if (chain[u] == -1) {
chain[u] = (1 - color[up_edge[u]]);
} else {
chain[u]++;
}
} else {
chain[u] = -1;
}
for (int i : adj[u]) {
int v = other(i, u);
if (up_edge[v] == -1) {
up_edge[v] = i;
color[i] = (chain[u] == -1 ? 1 - color[up_edge[u]] : pattern[chain[u] % 6]);
chain[v] = chain[u];
q.push(v);
}
}
}
}
int dist[N_MAX];
void bfs () {
fill(dist, dist + N, -1);
up_edge[0] = M; color[M] = 2;
dist[0] = 0;
queue <int> q;
q.push(0);
while (q.empty() == false) {
int u = q.front();
q.pop();
for (int i : adj[u]) {
int v = other(i, u);
if (dist[v] == -1) {
up_edge[v] = i;
dist[v] = dist[u] + 1;
color[i] = (color[up_edge[u]] + 1) % 3;
q.push(v);
} else if (dist[u] <= dist[v]){
color[i] = (color[up_edge[u]] + 1) % 3;
}
}
}
}
}
vector <int> Mark (int _N, int _M, int _A, int _B, vector <int> _U, vector <int> _V) {
N = _N; M = _M; A = _A; B = _B;
for (int i = 0; i < M; i++) {
edge_u[i] = _U[i]; edge_v[i] = _V[i];
adj[edge_u[i]].push_back(i);
adj[edge_v[i]].push_back(i);
}
if (B > 0) {
dfs();
} else {
bfs();
}
vector <int> X(M);
copy(color, color + M, X.begin());
for (int u = 0; u < N; u++) {
adj[u].clear();
up_edge[u] = 0;
}
return X;
}
#include <bits/stdc++.h>
#include "Catherine.h"
using namespace std;
namespace {
const int pattern[] = {0, 1, 0, 0, 1, 1};
int A, B;
vector <int> cols;
bool passed_test;
}
void Init (int _A, int _B) {
A = _A; B = _B;
cols.clear();
passed_test = false;
}
int Move (vector <int> cnt_col) {
if (B > 0) {
int deg = cnt_col[0] + cnt_col[1] + 1;
// First move
if (cols.empty() == true) {
deg--;
// If leaf, take the only option
if (deg == 1) {
passed_test = true;
cols.push_back((cnt_col[0] > 0 ? 0 : 1));
return cols.back();
}
// If not crossroad, take any option
if (deg == 2) {
if (cnt_col[0] == cnt_col[1]) {
cols.push_back(1);
cols.push_back(0);
} else if (cnt_col[0] > 0) {
cols.push_back(0);
cols.push_back(0);
} else {
cols.push_back(1);
cols.push_back(1);
}
return cols.back();
}
// If crossroad, take the only option with frequency 1
passed_test = true;
cols.push_back((cnt_col[0] == 1 ? 0 : 1));
return cols.back();
}
// If leaf, turn back
if (deg == 1) {
passed_test = true;
cols = {cols.back()};
return -1;
}
// If not crossroad, check for pattern
if (deg == 2) {
cols.push_back((cnt_col[0] > 0 ? 0 : 1));
if (passed_test == false && (int) cols.size() == 5) {
int down = false;
for (int i = 0; i < 6; i++) {
down = true;
for (int j = 0; j < 5; j++) {
if (cols[j] != pattern[(i + j) % 6]) {
down = false;
break;
}
}
if (down == true) {
break;
}
}
passed_test = true;
if (down == true) {
cols.pop_back();
cols = {cols.back()};
return -1;
}
}
return cols.back();
}
// If crossroad, check for count
passed_test = true;
if (cnt_col[0] == 0 || cnt_col[1] == 0) {
cols = {cols.back()};
return -1;
} else {
cols.push_back(1 - cols.back());
return cols.back();
}
} else {
if ((cnt_col[0] > 0) + (cnt_col[1] > 0) + (cnt_col[2] > 0) == 1) {
return (cnt_col[0] > 0 ? 0 : (cnt_col[1] > 0 ? 1 : 2));
} else {
return (cnt_col[0] == 0 ? 1 : (cnt_col[1] == 0 ? 2 : 0));
}
}
}
