#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const vector<int> period = {0, 1, 0, 0, 1, 1};
struct edge {
int from, to, idx;
};
vector< vector<edge> > g;
vector<int> solve1234(int N, int M, vector<int> U, vector<int> V) {
queue<int> q;
q.push(0);
vector<int> dist(N, -1), ans(M, -1);
dist[0] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& e : g[u]) {
if (dist[e.to] == -1) {
dist[e.to] = dist[u] + 1;
q.push(e.to);
}
}
}
for (int i = 0; i < M; i++) {
ans[i] = min(dist[U[i]], dist[V[i]]) % 3;
}
return ans;
}
vector<int> solve567(int N, int M, vector<int> U, vector<int> V) {
vector<int> prev(N, 1), was(N, 0), len(N, 0), ans(M, -1);
queue<int> q; q.push(0);
was[0] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
if ((int) g[u].size() == 2) {
if (len[u] == 0) {
if (prev[u] == 0) {
len[u] = 1;
}
}
}
for (auto& e : g[u]) {
if (!was[e.to]) {
if ((int) g[u].size() == 2 || u == 0) {
len[e.to] = len[u] + 1;
ans[e.idx] = period[len[u] % 6];
} else {
ans[e.idx] = !prev[u];
}
q.push(e.to);
was[e.to] = 1;
prev[e.to] = ans[e.idx];
}
}
}
return ans;
}
}
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
g.resize(N);
for (int i = 0; i < M; i++) {
g[U[i]].push_back({U[i], V[i], i});
g[V[i]].push_back({V[i], U[i], i});
}
if (A >= 3) {
return solve1234(N, M, U, V);
} else {
return solve567(N, M, U, V);
}
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const vector<int> period = {0, 1, 0, 0, 1, 1};
vector<int> cur;
int A, B, start = 1, rev = 0, last;
}
void Init(int A, int B) {
::A = A; ::B = B;
}
int Move(vector<int> y) {
if (A >= 3) {
for (int i = 0; i < 3; i++) {
if (y[i] > 0 && y[(i + 1) % 3] > 0) {
return i;
}
}
for (int i = 0; i < 3; i++) {
if (y[i] > 0) {
return i;
}
}
} else {
if (rev) {
int tmp = cur.back();
cur.pop_back();
if (cur.empty()) {
rev = 0;
}
return (last = tmp);
}
if (y[0] > 1 && y[1] > 0) {
start = 0;
return (last = 1);
}
if (y[0] > 1 && y[1] > 0) {
start = 0;
return (last = 0);
}
if (y[0] == 0 && y[1] == 0) {
start = 0;
return (last = -1);
}
if (start) {
if (y[0] > 0 && y[1] > 0 && !cur.empty()) {
start = 0;
return (last = !cur.back());
}
if (cur.empty()) {
if (y[0] == 1 && y[1] == 0) {
start = 0;
return 0;
}
if (y[1] == 1 && y[0] == 0) {
start = 0;
return 1;
}
}
for (int i = 0; i < 2; i++) {
if (y[i] > 0) {
if (cur.empty()) {
if (y[i] > 1) {
cur.push_back(i);
} else {
cur.push_back(!i);
}
} else if (y[i] > 1) {
start = 0;
return -1;
}
cur.push_back(i);
break;
}
}
if ((int) cur.size() == 5) {
start = 0;
for (int i = 0; i < 6; i++) {
int match = 1;
for (int j = 0; j < 5; j++) {
if (period[(i + j) % 6] != cur[j]) {
match = 0;
break;
}
}
if (match) {
rev = 1;
cur.pop_back();
cur.pop_back();
return -1;
}
}
}
if (!rev) {
return (last = cur.back());
}
} else {
if (y[0] == 1 && y[1] == 1) {
last = !last;
return last;
}
if (y[0] > 0) {
return (last = 0);
}
return (last = 1);
}
}
}
