#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=1;
if(c==-1||c==1) turn=0;
else turn=2;
}
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++) ret[i]=-1;
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){
queue<pair<int,pair<int,int> > > q;
q.push({0,{0,-1}});
int v[N];
memset(v,0,sizeof(v));
while(!q.empty()){
int a=q.front().first,b=q.front().second.first,c=q.front().second.second;
q.pop();
if(v[b]) continue;
v[b]=1;
for(auto i:adj[b]){
if(ret[i.second]==-1) ret[i.second]=a%3;
if(!v[i.first]) q.push({a+1,{i.first,0}});
}
}
return ret;
}
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;
int mode=0;
void Init(int A, int B){
start=true;
confuse=false;
if(A>2) mode=1;
}
int pre=-1;
string cur="";
int Move(vector<int> y){
if(mode){
if(y[0]&&y[1]) return 0;
else if(y[1]&&y[2]) return 1;
else if(y[0]&&y[2]) return 2;
else if(y[0]) return 0;
else if(y[1]) return 1;
else if(y[2]) return 2;
else{
assert(false);
return -1;
}
}
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]==2){
cur+="00";
return pre=0;
}
else if(y[1]==2){
cur+="11";
return pre=1;
}
else{
cur+="01";
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;
}
confuse=false;
return pre=1-pre;
}
else if(y[0]+y[1]==0){
confuse=false;
return -1;
}
else{
if(cur.length()==4){
if(y[0]) cur+="0";
else cur+="1";
if(cur=="10100"||cur=="01001"||cur=="10011"||cur=="00110"||cur=="01101"||cur=="11010"){
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;
}
