#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
namespace {
vector<int> res;
vector<ii> G[20007];
vector<ii> ch[20007];
int ord[] = {0, 0, 1, 0, 1, 1};
bool vis[20007];
int top[20007];
bool intree[20007];
void dfs(int w = 0, int p = -1, int o = -1, int c = 0) {
int deg = G[w].size();
if(p != -1) deg--;
for(ii u : G[w]) {
if(u.X != p) {
if(deg > 1) {
res[u.Y] = c ^ 1;
dfs(u.X, w, -1, c ^ 1);
} else {
if(o == -1) {
if(c == 0)
o = 4;
else
o = 0;
}
res[u.Y] = ord[o];
dfs(u.X, w, (o + 1) % 6, ord[o]);
}
}
}
}
void dfs2(int w = 0, int p = -1, int c = 0) {
for(ii u : ch[w]) {
if(u.X != p) {
res[u.Y] = c;
intree[u.Y] = 1;
top[u.X] = c;
dfs2(u.X, w, (c + 1) % 3);
}
}
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
res.resize(M);
for(int i = 0 ; i < M ; i++) {
int a = U[i];
int b = V[i];
G[a].emplace_back(b, i);
G[b].emplace_back(a, i);
}
if(A == 2) {
dfs();
} else {
queue<int> Q;
vis[0] = 1;
Q.push(0);
while(!Q.empty()) {
int w = Q.front();
Q.pop();
for(ii u : G[w]) {
if(!vis[u.X]) {
ch[w].emplace_back(u);
vis[u.X] = 1;
Q.push(u.X);
}
}
}
dfs2();
for(int i = 0 ; i < M ; i++) {
if(!intree[i]) {
if(top[U[i]] == top[V[i]])
res[i] = (top[U[i]] + 1) % 3;
else {
int a = top[U[i]];
int b = top[V[i]];
if(a > b) swap(a, b);
if(a == 0 && b == 1) res[i] = 1;
if(a == 0 && b == 2) res[i] = 0;
if(a == 1 && b == 2) res[i] = 2;
}
}
}
}
for(int i = 0 ; i < M ; i++)
cerr << res[i] << " ";
cerr << endl;
return res;
}
#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B;
vector<int> hist;
bool up;
int ord[] = {0, 0, 1, 0, 1, 1};
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(std::vector<int> y) {
if(A > 2) {
if((y[0] ? 1 : 0) + (y[1] ? 1 : 0) + (y[2] ? 1 : 0) == 1) {
int k = 0;
if(y[1]) k = 1;
if(y[2]) k = 2;
return k;
}
if(y[0] && y[1]) return 0;
if(y[0] && y[2]) return 2;
return 1;
}
if(up) {
if(!y[0]) {
hist.push_back(1);
return 1;
}
if(!y[1]) {
hist.push_back(0);
return 0;
}
hist.push_back(hist.back() ^ 1);
return hist.back();
}
if(hist.empty() && y[0] + y[1] == 1) {
int k = 0;
if(!y[0]) k = 1;
hist.push_back(k);
up = 1;
return k;
}
int z[2];
z[0] = y[0];
z[1] = y[1];
if(!hist.empty())
z[hist.back()]++;
if(z[0] > 1 && z[1] == 1) {
hist.push_back(1);
up = true;
return y[1] ? 1 : -1;
}
if(z[1] > 1 && z[0] == 1) {
hist.push_back(0);
up = true;
return y[0] ? 0 : -1;
}
if(y[0] == 0 && y[1] == 0) {
hist.push_back(hist.back());
up = true;
return -1;
}
if(hist.size() < 4) {
vector<int> V;
for(int x = 0 ; x < y[0] ; x++) V.push_back(0);
for(int x = 0 ; x < y[1] ; x++) V.push_back(1);
if(y[0] + y[1] == 2) {
hist.push_back(V[0]);
hist.push_back(V[1]);
return V[1];
}
hist.push_back(V[0]);
return V[0];
}
bool down = false;
int k = 0;
if(!y[0]) k = 1;
for(int i = 0 ; i < 6 ; i++) {
if(hist[0] == ord[i] && hist[1] == ord[(i+1) % 6] && hist[2] == ord[(i+2) % 6]
&& hist[3] == ord[(i+3) % 6] && k == ord[(i+4) % 6]) {
down = true;
}
}
if(down) {
hist.push_back(hist.back());
up = 1;
return -1;
}
up = 1;
hist.push_back(k);
return k;
}
