#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
namespace {
const int N=100050;
int dist[N];
vector<int> E[N];
void AddEdge(int u,int v){E[u].pb(v);E[v].pb(u);}
void BFS(int n,int m){
queue<int> q;
q.push(0);dist[0]=1;
while(q.size()){
int u=q.front();
q.pop();
for(int v:E[u])if(!dist[v]){
dist[v]=dist[u]+1;
q.push(v);
}
}
}
vector<int> Solve(int n,int m,vector<int> u,vector<int> v){
vector<int> col;
for(int i=0;i<m;i++){
int a=u[i],b=v[i];
if(dist[a]>dist[b])swap(a,b);
if(dist[a]==dist[b])col.pb((dist[b]+1)%3);
else col.pb(dist[b]%3);
}
return col;
}
vector<int> Solve2(int n,int m,vector<int> u,vector<int> v){
vector<int> col(m);
/*for(int i=0;i<m;i++){
int a=u[i],b=v[i];
if(dist[a]>dist[b])swap(a,b);
if(dist[a]==dist[b])col.pb((dist[b]+1)%2);
else col.pb(dist[b]%2);
}*/
vector<vector<pii>> E(n);
for(int i=0;i<m;i++)E[u[i]].pb({v[i],i}),E[v[i]].pb({u[i],i});
vector<int> patern={0,1,0,0,1,1};
function<void(int,int,int)> DFS=[&](int u,int p,int c){
int deg=E[u].size();
if(p!=-1)deg--;
if(u){
if(deg==1)c=(c+1)%6;
else c=patern[c]^1;
}
for(auto e:E[u])if(e.first!=p){
col[e.second]=patern[c];
DFS(e.first,u,c);
}
};
DFS(0,-1,0);
return col;
}
} // namespace
vector<int> Mark(int n,int m,int a,int b,vector<int> u,vector<int> v){
for(int i=0;i<m;i++)AddEdge(u[i],v[i]);
BFS(n,m);
if(a>2)return Solve(n,m,u,v);
else return Solve2(n,m,u,v);
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
namespace {
int a,b,now,last,turn;
bool fir,sibaj;
vector<int> bits,patern={0,1,0,0,1,1};
bool Check(){
for(int i=0;i<6;i++){
bool ok=1;
for(int j=0;j<5;j++){
if(bits[j]!=patern[(i+j)%6])
ok=0;
}
if(ok)return 1;
}
return 0;
}
} // namespace
void Init(int a,int b){
::a=a;
::b=b;
fir=1;
turn=0;
last=-1;
if(a==2){
now=1;
sibaj=0;
bits.clear();
}
}
int Move(vector<int> y){
if(a>2){
int cnt=0;
for(int i=0;i<3;i++)if(y[i]!=0)cnt++;
if(cnt<2){
assert(cnt==1);
for(int i=0;i<3;i++)if(y[i]!=0)now=i;
}else{
assert(cnt==2);
if(y[0]==0)now=1;
else if(y[1]==0)now=2;
else now=0;
}
return now;
}else{
turn++;
int deg=y[0]+y[1]+(turn!=1);
if(sibaj){
if(y[last^1])return last^=1;
else return last;
}else if(deg>2){
sibaj=1;
if(turn!=1)y[last]++;
int col;
if(y[0]==1)col=0;
else col=1;
if(last==col)return -1;
else return last=col;
}else if(deg==1){
sibaj=1;
if(turn==1)return last=(y[0]?0:1);
else return -1;
}else{
if(turn==1){
for(int i=0;i<y[0];i++)bits.pb(0);
for(int i=0;i<y[1];i++)bits.pb(1);
return last=bits.back();
}else if(turn<4){
int col;
if(y[0])col=0;
else col=1;
bits.pb(col);
return last=col;
}else if(turn==4){
int col;
if(y[0])col=0;
else col=1;
bits.pb(col);
sibaj=1;
if(Check())return -1;
else return last=col;
}
}
}
}
