#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
vector<vector<int>> g(N);
for (int i = 0; i < M; i++) {
g[U[i]].push_back(i);
g[V[i]].push_back(i);
}
vector<int> a;
if (A > 2) a = {0, 1, 2};
else a = {0, 1, 0, 0, 1, 1};
vector<int> idx(N, -1), X(M, -1);
queue<int> bfs;
bfs.push(idx[0] = 0);
while (bfs.size()) {
int x = bfs.front();
bfs.pop();
for (int y : g[x]) {
if (X[y] < 0) X[y] = a[idx[x]];
int z = U[y] ^ V[y] ^ x;
if (idx[z] < 0) {
if (g[y].size() > 2 && A == 2) idx[z] = !a[idx[x]];
else idx[z] = (idx[x] + 1) % a.size();
bfs.push(z);
}
}
}
// for (int i = 0; i < N; i++) {
// cout << i << ": ";
// for (int j : g[i]) cout << X[j] << " ";
// cout << endl;
// }
return X;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B, lst = -1;
bool amb = true; // whether direction is currently ambiguous
string signs = "";
string ord = "010011010011";
}
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(vector<int> y) {
if (A > 2) {
if (!y[0]) return y[1] ? 1 : 2;
if (!y[1]) return y[2] ? 2 : 0;
if (!y[2]) return y[0] ? 0 : 1;
assert(false); // we should never reach here
}
int opt = accumulate(y.begin(), y.end(), 0) + (lst >= 0);
if (opt > 2) { // at junction
amb = false;
return lst = (y[1] + max(lst, 0) == 1); // pick mark which only has one road---since deg > 2, this is unique
}
else if (opt == 1) { // at leaf
amb = false;
if (lst >= 0) return -1;
return lst = y[1];
}
else if (!amb) { // at deg 2 node, direction known
return lst = y[1]; // just pick the one edge which is not the one we just traversed
}
else { // at deg 2 node, direction still ambiguous
for (int _ = 0; _ < y[0]; _++) signs.push_back('0');
for (int _ = 0; _ < y[1]; _++) signs.push_back('1');
if (signs.size() == 5) { // now we can decide whether we're going in the right direction
amb = false;
for (int i = 0; i < 6; i++) if (signs == ord.substr(i, 5)) return -1;
}
if (y[0] && y[1]) return lst = 1;
return lst = y[1];
}
}
