#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
namespace {
} // namespace
int f(int x){
return (x == 1 || x == 4 || x == 5);
}
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
vector<int> adjlist[N];
int dist[N];
int p[N];
vector<int> ans;
queue<int> q;
for (int i = 0; i < M; i++){
adjlist[U[i]].push_back(V[i]);
adjlist[V[i]].push_back(U[i]);
}
ans.resize(M);
if (A >= 3){
memset(dist,-1,sizeof(dist));
dist[0] = 0;
p[0] = 0;
q.push(0);
while (q.size()){
int u = q.front(); q.pop();
for (auto v : adjlist[u]){
if (dist[v] == -1){
//printf("%d -> %d\n",u,v);
p[v] = u;
dist[v] = dist[u]+1;
q.push(v);
}
}
}
for (int i = 0; i < M; i++){
if (dist[U[i]] > dist[V[i]]) swap(U[i],V[i]);
int d = (dist[V[i]]-dist[U[i]]);
if (p[V[i]] == U[i]) {
ans[i] = dist[U[i]]%3;
//printf("edge %d-%d, dist %d,%d: mark %d\n",U[i],V[i],dist[U[i]],dist[V[i]],ans[i]);
}
else ans[i] = -1;
}
for (int i = 0; i < M; i++){
if (ans[i] == -1){
ans[i] = dist[U[i]]%3;
//printf("useless edge %d-%d dist %d,%d: mark %d\n",U[i],V[i],dist[U[i]],dist[V[i]],ans[i]);
}
}
}
else{
memset(dist,-1,sizeof(dist));
dist[0] = 0;
p[0] = 0;
q.push(0);
while (q.size()){
int u = q.front(); q.pop();
int branch = adjlist[u].size() > 2;
if (branch){
dist[u] = f(dist[p[u]])^1;
}
for (auto v : adjlist[u]){
if (dist[v] == -1){
//printf("%d -> %d\n",u,v);
p[v] = u;
dist[v] = (dist[u]+1)%6;
q.push(v);
}
}
}
for (int i = 0; i < M; i++){
if (p[U[i]] == V[i]) swap(U[i],V[i]);
ans[i] = f(dist[U[i]]);
//printf("%d %d %d\n",U[i],V[i],ans[i]);
}
}
return ans;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B;
int sure = 0;
vector<int> sofar;
int prv = -2;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(std::vector<int> y) {
//printf("new move %d %d, prev %d\n",y[0],y[1],prv);
//printf("wasted %d so far, sure ? %d\n",(int)sofar.size(),sure);
if (A >= 3){
if (prv == -2){
if (y[0] == 0) return prv = y[1]?1:2;
else if (y[1] == 0) return prv = y[2]?2:0;
else if (y[2] == 0) return prv = y[0]?0:1;
}
else{
return prv = (prv+2)%3;
}
}
else{
int total = y[0]+y[1];
int cur = y[0]==1?0:1;
if (sure){
if (total >= 2){
cur = prv^1;
}
return prv = cur;
}
else if (sofar.empty()){
if (total == 1){
sure = true;
return prv = cur;
}
else if (total == 2){
cur = y[0]?0:1;
if (y[cur] == 2) sofar.push_back(cur);
else sofar.push_back(cur^1);
sofar.push_back(cur);
return prv = cur;
}
else{
sure = true;
assert(y[0] != 0 && y[1] != 0);
return prv = cur;
}
}
else if ((int)sofar.size() == 4){
sure = true;
if (total == 0){
return -1;
}
int CUR = 8*sofar[0] + 4*sofar[1] + 2*sofar[2]+sofar[3];
int need = -1;
if (CUR == 9 || CUR == 11 || CUR == 6) need = 0;
else if (CUR == 12 || CUR == 2 || CUR == 5) need = 1;
//printf("so far visited %d %d %d %d -> %d\n",sofar[0],sofar[1],sofar[2],sofar[3],need);
if (need == -1 || y[need] == 0){
return -1;
}
else return prv = need;
}
else{
if (total == 0){
sure = true;
return -1;
}
if (total > 1){
sure = true;
if (y[0] == 0 || y[1] == 0){
return -1;
}
cur = prv^1;
assert(y[cur]);
return prv = cur;
}
else{
sofar.push_back(cur);
return prv = cur;
}
}
}
}
