#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];
void dfs (int u, int chain = -1) {
if ((int) adj[u].size() == 2 && u != 0) {
if (chain == -1) {
chain = 1 - color[up_edge[u]];
} else {
chain++;
}
} else {
chain = -1;
}
for (int i : adj[u]) {
if (i != up_edge[u]) {
int v = other(i, u);
up_edge[v] = i;
color[i] = (chain == -1 ? 1 - color[up_edge[u]] : pattern[chain % 6]);
dfs(v, chain);
}
}
}
void dfs () {
up_edge[0] = N;
color[0] = 0;
dfs(0);
}
}
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;
assert(M == N - 1);
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);
}
dfs();
vector <int> X(M);
copy(color, color + M, X.begin());
return X;
}
#include <bits/stdc++.h>
#include "Catherine.h"
using namespace std;
namespace {
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) {
int now = (cols.empty() == false ? 1 - cols.back() : 0);
if (cnt_col[now] > 0) {
cols.push_back(now);
} else if (cnt_col[1 - now] > 0) {
cols.push_back(1 - now);
} else {
passed_test = true;
cols = {cols.back()};
return -1;
}
int deg = cnt_col[0] + cnt_col[1] + ((int) cols.size() != 1);
if (cnt_col[cols.back()] > 1 && deg > 2) {
if ((int) cols.size() == 1) {
cols.back() = 1 - cols.back();
} else {
passed_test = true;
cols = {cols.back()};
return -1;
}
}
if (passed_test == false && (int) cols.size() == 6) {
passed_test = true;
bool ok = true;
for (int i = 0; i < (int) cols.size(); i++) {
if (cols[i] == 0 && cols[(i + 1) % 6] == 0) {
ok = (cols[(i + 2) % 6] != cols[(i + 3) % 6]);
}
}
if (ok == false) {
cols.pop_back();
cols = {cols.back()};
return -1;
}
}
return cols.back();
}
