#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
const int MN = 2e4+5;
int n, i, dep[MN], par[MN], col[MN], vs[MN], hm[MN];
vi ans; vector<pii> adj[MN];
queue<int> q;
vi Mark(int N,int M,int A,int B,vi U,vi V){
ans.resize(M);
for(i=0;i<M;i++){
adj[U[i]].pb({V[i],i});
adj[V[i]].pb({U[i],i});
}
if(A>=3){
vs[0] = 1; q.push(0);
while(q.size()){
int x = q.front(); q.pop();
for(auto v : adj[x]){
if(!vs[v.first]){
vs[v.first] = 1;
dep[v.first] = dep[x]+1;
ans[v.second] = dep[x]%3;
q.push(v.first);
}
else ans[v.second]=min(dep[x],dep[v.first])%3;
}
}
return ans;
}
else{
int msk[]={0,0,1,0,1,1};
q.push(0);
while(q.size()){
int x = q.front(); q.pop();
if(x&&adj[x].size()==2){
hm[x] = 1;
if(hm[par[x]]) dep[x]=(dep[par[x]]+1)%6;
else if(col[x]==0) dep[x]=0;
else dep[x]=2;
for(auto v : adj[x]){
if(v.first==par[x]) continue;
ans[v.second]=col[v.first]=msk[(dep[x]+1)%6];
par[v.first]=x;
q.push(v.first);
}
}
else{
for(auto v : adj[x]){
if(v.first==par[x]) continue;
ans[v.second]=col[v.first]=!col[x];
par[v.first]=x;
q.push(v.first);
}
}
}
return ans;
}
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
int lst=-1, sub, ok, pat[]={0,0,1,0,1,1};
vi guess;
void Init(int A,int B){
if(A>=3) sub=1;
else sub=2;
}
bool match(){
for(int i=0;i<6;i++){
int tmp = 0;
for(int j=0;j<guess.size();j++){
if(guess[j]!=pat[(i+j)%6]){tmp=1;break;}
}
if(!tmp) return 1;
}
return 0;
}
int Move(vi cnt){
if(sub==1){
for(int i=0;i<3;i++){
if(cnt[i]&&!cnt[(i+2)%3]) return i;
}
}
else{
int c=0;
if(lst!=-1) cnt[lst]++;
for(auto v : cnt) c += v;
if(c!=2) ok=1;
if(ok){
if(c==2){
cnt[lst]--;
if(cnt[0]){lst=0;return lst;}
else{lst=1;return lst;}
}
if(lst==-1){
if(cnt[0]==1){lst=0; return 0;}
else{lst=1; return 1;}
}
if(cnt[0]==1&&cnt[1]==1){lst=!lst;return lst;}
if(cnt[lst]==1) return -1;
else{lst=!lst; return lst;}
}
else{
if(lst==-1){
if(cnt[0]){
guess.pb(0);
if(cnt[1]){guess.pb(1); lst=1;}
else{guess.pb(0); lst=0;}
}
else{
guess.pb(1); guess.pb(1);
lst = 1;
}
return lst;
}
else{
cnt[lst]--;
int ot=0;
if(cnt[1]) ot=1;
guess.pb(ot);
bool d1 = match();
reverse(guess.begin(),guess.end());
bool d2 = match();
reverse(guess.begin(),guess.end());
if(d1!=d2){
ok = 1;
if(d1) return -1;
else{lst = ot; return ot;}
}
lst = ot;
return ot;
}
}
}
}
