#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
int seq[6]={0,1,0,0,1,1};
vector<int> col,par,AL[200005];
void dfs(int u,int pv){
if(AL[u].size()>2){
for(int v:AL[u]){
if(v==par[u])continue;
col[v]=(seq[pv]==0)?1:0;
par[v]=u;
dfs(v,(seq[pv]==0)?1:0);
}
}
else{
for(int v:AL[u]){
if(v==par[u])continue;
col[v]=seq[(pv+1)%6];
par[v]=u;
dfs(v,(pv+1)%6);
}
}
}
vector<int> Mark(int N,int M,int A,int B,vector<int> U,vector<int> V){
if(A>=3){
vector<int> dist(N,-1);
for(int i=0;i<M;++i){
AL[U[i]].push_back(V[i]);
AL[V[i]].push_back(U[i]);
}
queue<int> q;
dist[0]=0;q.push(0);
while(!q.empty()){
int u=q.front();q.pop();
for(int v:AL[u]){
if(dist[v]==-1){
dist[v]=dist[u]+1;
q.push(v);
}
}
}
vector<int> X(M);
for(int i=0;i<M;++i){
if(dist[U[i]]!=dist[V[i]])X[i]=(dist[U[i]]+dist[V[i]])%3;
else X[i]=(2*dist[U[i]]+1)%3;
}
return X;
}
else{
col.resize(N);
par.resize(N,-1);
for(int i=0;i<M;++i){
AL[U[i]].push_back(V[i]);
AL[V[i]].push_back(U[i]);
}
dfs(0,5);
vector<int> X(M);
for(int i=0;i<M;++i){
if(par[U[i]]==V[i])X[i]=col[U[i]];
else X[i]=col[V[i]];
}
return X;
}
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
bool tree=true,found=false;
int mask,cnt;
int pv=-1;
int check[6]={25,18,5,11,22,12};
void Init(int A, int B){
if(A>=3)tree=false;
}
int Move(vector<int> y){
if(!tree){
if(y[0]==0&&y[1]==0)return 2;
if(y[0]==0&&y[2]==0)return 1;
if(y[1]==0&&y[2]==0)return 0;
if(y[0]==0)return 2;
if(y[1]==0)return 0;
if(y[2]==0)return 1;
}
else{
//handle degree >=3
if(pv==-1&&y[0]+y[1]>=3){
found=true;
return pv=(y[0]>1)?1:0;
}
if(pv!=-1&&y[0]+y[1]>=2){
found=true;
if(y[0]+(pv==0)>1)return (pv==1)?-1:pv=1;
else return (pv==0)?-1:pv=0;
}
//if we know which way to go
if(found)return pv=(y[0]==1)?0:1;
//first node
if(pv==-1){
//leaf node
if(y[0]==0&&y[1]==1){
found=true;
return pv=1;
}
if(y[1]==0&&y[0]==1){
found=true;
return pv=0;
}
if(y[0]==1&&y[1]==1){
mask=1;
++cnt;
return pv=1;
}
else if(y[0]==2){
mask=0;
++cnt;
return pv=0;
}
else{
mask=3;
++cnt;
return pv=1;
}
}
else{
//reached a leaf
if(y[0]==0&&y[1]==0){
found=true;
return -1;
}
mask<<=1;
if(y[0]==0)++mask;
if(cnt==3){
bool in=false;
for(int i=0;i<6;++i){
if(mask==check[i])in=true;
}
found=true;
if(in)return (y[0]==0)?1:0;
else return -1;
}
else{
++cnt;
return pv=(y[0]==0)?1:0;
}
}
return pv=0;
}
}
