#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
string str="001011";
const int N=20005;
vector<int> v,adj[N+1],deg(N),e(N);
const int INF=1e9;
void dfs(int k,int pa,int dis,int up){
for(int i:adj[k]){
int j=e[i]^k;
if(j==pa)continue;
if(deg[k]<=2){
v[i]=str[dis%6]-'0';
dfs(j,k,dis+1,v[i]);
}
else{
v[i]=up^1;
if(v[i]==1)dfs(j,k,3,v[i]);
else dfs(j,k,1,v[i]);
}
}
}
vector<int> Mark(int N, int M, int A, int B,vector<int> U, vector<int> V) {
if(A>=3){
vector<int> v(M,-1),adj[N+1];
queue<int> q;
vector<int> dis(N+1,INF);
for(int i=0;i<M;i++){
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
}
q.push(0);
dis[0]=0;
while(q.size()){
int p=q.front();
q.pop();
for(int j:adj[p]){
if(v[j]==-1){
v[j]=dis[p]%3;
}
}
for(int i:adj[p]){
int j=(U[i]==p?V[i]:U[i]);
if(dis[j]==INF){
dis[j]=dis[p]+1;
v[i]=dis[p]%3;
q.push(j);
}
}
}
return v;
}
v.resize(M,-1);
queue<int> q;
vector<int> dis(N+1,INF);
for(int i=0;i<M;i++){
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
deg[U[i]]++;
deg[V[i]]++;
e[i]=U[i]^V[i];
}
dfs(0,0,0,0);
return v;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
int last=-1,sure=0;
vector<int> tmp={0,0,1,0,1,1};
vector<int> rec;
int a,b;
void Init(int A, int B) {
a=A,b=B;
}
int Move2(vector<int> y) {
//cout<<y[0]<<' '<<y[1]<<' '<<last<<endl;
if(sure){
int tot=y[0]+y[1];
if(min(y[0],y[1])==0){
return last=(y[0]?0:1);
}
else{
if(y[last^1]==0)cout<<"NO"<<endl;
return last=last^1;
}
}
if(last==-1){
int tot=y[0]+y[1];
if(tot==1){
sure=1;
last=(y[0]?0:1);
return last;
}
else if(tot==2){
if(y[0]&&y[1]){
rec.push_back(0);
rec.push_back(1);
return last=1;
}
else if(y[0]==2){
rec.push_back(0);
rec.push_back(0);
return last=0;
}
else{
rec.push_back(1);
rec.push_back(1);
return last=1;
}
}
else{
sure=1;
last=(y[0]>y[1]?1:0);
assert(y[last]!=0);
return last;
}
}
else{
int tot=y[0]+y[1];
if(tot==0){
sure=1;
return -1;
}
else if(tot==1){
rec.push_back((y[0]?0:1));
if(rec.size()==5){
int flag=0;
for(int i=0;i<6;i++){
vector<int> a(tmp.begin(),tmp.begin()+5);
if(a==rec){
flag=1;
break;
}
rotate(tmp.begin(),tmp.begin()+1,tmp.end());
}
if(flag==0){
sure=1;
return last=(y[0]?0:1);
}
else{
sure=1;
return -1;
}
}
else{
last=(y[0]?0:1);
return last;
}
}
else{
y[last]++;
if(y[0]==1){
int t=(last==0?-1:0);
last=0;
sure=1;
return t;
}
else{
int t=(last==1?-1:1);
last=1;
sure=1;
return t;
}
}
}
assert(false);
}
int Move3(vector<int> y) {
if(y[0]==0&&y[1]==0)return 2;
if(y[1]==0&&y[2]==0)return 0;
if(y[2]==0&&y[0]==0)return 1;
if(y[0]&&y[1])return 0;
if(y[1]&&y[2])return 1;
if(y[2]&&y[0])return 2;
}
int Move(vector<int> y){
if(a==2){
return Move2(y);
}
else{
return Move3(y);
}
}
