#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > adj[20005],tadj[20005];
int ans[20005];
bool start=false;
int turn=0;
string s="101001";
void dfs(int x, int p, int c){
int child=0;
for(auto i:tadj[x]){
if(i.first==p) continue;
child++;
}
if(child>1){
start=false;
turn=0;
for(auto i:tadj[x]){
if(i.first==p) continue;
ans[i.second]=1-c;
dfs(i.first,x,1-c);
}
}
else if(child==1){
if(!start){
start=true;
turn=0;
}
for(auto i:tadj[x]){
if(i.first==p) continue;
ans[i.second]=s[turn]-'0';
turn++;
turn%=6;
dfs(i.first,x,ans[i.second]);
}
}
}
vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V){
vector<int> ret(M);
for(int i=0; i<M; i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
if(A>2){
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > pq;
pq.push({0,{0,-1}});
int v[N],tree[M];
memset(tree,0,sizeof(tree));
memset(v,0,sizeof(v));
while(!pq.empty()){
int a=pq.top().first,b=pq.top().second.first,c=pq.top().second.second;
pq.pop();
if(v[b]) continue;
v[b]=1;
if(c!=-1){
tree[c]=1;
}
for(auto i:adj[b]){
if(!v[i.first]) pq.push({a+1,{i.first,i.second}});
}
}
for(int i=0; i<M; i++){
if(!tree[i]) ret[i]=ans[i]=2;
else{
tadj[U[i]].push_back({V[i],i});
tadj[V[i]].push_back({U[i],i});
}
}
}
else{
for(int i=0; i<M; i++){
tadj[U[i]].push_back({V[i],i});
tadj[V[i]].push_back({U[i],i});
}
}
dfs(0,-1,1);
for(int i=0; i<M; i++) ret[i]=ans[i];
return ret;
}
#include <bits/stdc++.h>
using namespace std;
bool start=true,confuse=false;
void Init(int A, int B){
start=true;
confuse=false;
}
int pre=-1;
string cur="";
int Move(vector<int> y){
if(!start&&!confuse){
if(y[0]+y[1]==1){
if(y[0]) return pre=0;
else return pre=1;
}
else if(y[0]+y[1]==0) return -1;
//assert(y[1-pre]==1);
return pre=1-pre;
}
if(start){
start=false;
if(y[0]+y[1]==2){
confuse=true;
if(y[0]){
cur+="0";
return pre=0;
}
else{
cur+="1";
return pre=1;
}
}
else{
if(y[0]==1) return pre=0;
else if(y[1]==1) return pre=1;
else{
assert(false);
return -1;
}
}
}
if(confuse){
if(y[0]+y[1]>1){
if(y[0]==0||y[1]==0){
confuse=false;
return -1;
}
return pre=1-pre;
}
else if(y[0]+y[1]==0){
confuse=false;
return -1;
}
else{
if(cur.length()==6){
if(cur=="101001"||cur=="010011"||cur=="100110"||cur=="001101"||cur=="011010"||cur=="110100"){
cur="";
confuse=false;
return -1;
}
else{
cur="";
confuse=false;
if(y[0]) return pre=0;
else return pre=1;
}
}
if(y[0]){
cur+="0";
return pre=0;
}
else{
cur+="1";
return pre=1;
}
}
}
return 0;
}
