#include "Anthony.h"
#include <vector>
#include <cstdio>
#include <queue>
#include <cassert>
#include <algorithm>
#include <cstdlib>
using namespace std;
namespace {
vector<int> graph[20005];
int dists[20005], seen[20005];
queue<int> bfs;
// dfs
vector<int> seq = { 0, 1, 1, 0, 0, 1 };
vector<int> ch[20005];
int depth[20005], col[20005];
void dfs(int x, int p, int state) {
for (int v : graph[x]) if (v != p) {
ch[x].push_back(v);
depth[v] = depth[x] + 1;
}
if (ch[x].size() == 0) return;
if (ch[x].size() == 1) {
col[ch[x][0]] = seq[(state + 1) % 6];
dfs(ch[x][0], x, (state + 1) % 6);
} else {
for (int v : ch[x]) {
col[v] = seq[state] ^ 1;
dfs(v, x, col[v]);
}
}
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
vector<int> res;
for (int i = 0; i < M; i++) {
graph[U[i]].push_back(V[i]);
graph[V[i]].push_back(U[i]);
}
if (A >= 3) {
seen[0] = 1;
bfs.push(0);
while (!bfs.empty()) {
int u = bfs.front(); bfs.pop();
for (int v : graph[u]) if (!seen[v]) {
seen[v] = 1;
dists[v] = dists[u] + 1;
bfs.push(v);
}
}
//for (int i = 0; i < N; i++) fprintf(stderr, "dists[%d]: %d\n", i, dists[i]);
for (int i = 0; i < M; i++) {
int u = U[i], v = V[i];
if (dists[u] != dists[v]) {
res.push_back(min(dists[u], dists[v]) % 3);
} else {
res.push_back(dists[u] % 3);
}
}
} else {
dfs(0, 0, 1);
for (int i = 0; i < M; i++) {
int u = U[i], v = V[i];
if (depth[u] > depth[v]) swap(u, v);
res.push_back(col[v]);
}
}
for (int i = 0; i < M; i++) fprintf(stderr, "Edge %d - %d marked %d\n", U[i], V[i], res[i]);
return res;
}
#include "Catherine.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cassert>
using namespace std;
namespace {
int A, B;
int yay = 0;
int last = 0;
int initial = 1;
vector<int> seq = { 0, 1, 1, 0, 0, 1 };
vector<int> steps;
} // namespace
void Init(int A, int B) {
steps.clear();
initial = 1;
yay = 0;
last = 0;
::A = A;
::B = B;
}
int _move(std::vector<int> y) {
if (A >= 3) {
if (y[0] == 0) {
if (y[1] == 0) return 2;
return 1;
} else if (y[1] == 0) {
if (y[2] == 0) return 0;
return 2;
} else {
return 0;
}
} else {
if (y[0] == 0 && y[1] == 0) {
steps.clear();
yay = 1;
initial = 0;
return -1;
} else if (initial && y[0] + y[1] == 2) {
// Go in a random direction
steps.push_back(y[1] > 0);
initial = 0;
return last = y[1] > 0;
} else if (y[0] + y[1] == 1) {
if (yay) return last = (y[1] == 1);
steps.push_back(y[1] == 1);
int sz = steps.size();
if (sz >= 4) {
int cooked = 0;
if (steps[sz-4] == 1) {
if (steps[sz-3] == 1) {
if (steps[sz-2] == 0 && steps[sz-1] == 0) cooked = 1;
} else {
if (steps[sz-2] == 1 && steps[sz-1] == 1) cooked = 1;
}
} else {
if (steps[sz-3] == 1) {
if (steps[sz-2] == 0 && steps[sz-1] == 1) cooked = 1;
} else {
if (steps[sz-2] == 1 && steps[sz-1] == 0) cooked = 1;
}
}
if (cooked) {
yay = 1;
initial = 0;
return -1;
}
}
return last = (y[1] == 1);
} else {
steps.clear();
if (y[0] == 0 || y[1] == 0) {
yay = 1;
initial = 0;
return -1;
} else {
vector<int> rt = { y[0], y[1] };
if (!initial) rt[last]++;
yay = 1;
initial = 0;
return last = (rt[1] == 1);
}
}
}
}
int Move(std::vector<int> y) {
int res = _move(y);
return res;
}
