#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
namespace
{
pii a={0,0},b={0,1},c={1,1};
vector<pii> vec={b,c,b,b,b,a};
map<pii,int> myind;
int INF=1e9;
vector<int> muchii[20005];
vector<pii> g;
int dist[20005];
int par[20005];
int n,m;
void bfs()
{
for(int i=0;i<n;i++)
dist[i]=INF;
dist[0]=0;
queue<int> coada;
coada.push(0);
while(!coada.empty())
{
int nod=coada.front();
coada.pop();
for(int i:muchii[nod])
if(dist[i]>dist[nod]+1)
{
dist[i]=dist[nod]+1;
coada.push(i);
}
}
}
int garbage(int x)
{
if(x%3==0)
return 0;
if(x%3==1)
return 1;
return 2;
}
vector<int> subtask14()
{
vector<int> sol;
for(int i=0;i<m;i++)
{
int a=g[i].first,b=g[i].second;
if(dist[a]>dist[b])
swap(a,b);
int val=garbage(dist[a]);
sol.push_back(val);
}
return sol;
}
vector<int> sol;
void dfs(int nod)
{
if(nod==0)
{
for(int i:muchii[nod])
if(i!=par[nod])
{
par[i]=nod;
int ind=myind[{nod,i}];
sol[ind]=0;
dfs(i);
}
return;
}
if(muchii[nod].size()>=3)
{
int c=sol[myind[{nod,par[nod]}]];
c=1-c;
for(int i:muchii[nod])
if(i!=par[nod])
{
par[i]=nod;
int ind=myind[{nod,i}];
sol[ind]=c;
dfs(i);
}
return;
}
int cul=sol[myind[{nod,par[nod]}]];
int poz;
if(cul==0)
poz=5;
else
poz=1;
while(true)
{
if(muchii[nod].size()>2)
{
dfs(nod);
break;
}
if(muchii[nod].size()==1)
break;
int nxt=(muchii[nod][0]^muchii[nod][1]^par[nod]);
int c=sol[myind[{nod,par[nod]}]];
c=(vec[poz].first^vec[poz].second^c);
sol[myind[{nod,nxt}]]=c;
par[nxt]=nod;
poz++;
poz%=6;
nod=nxt;
}
}
}
/// a={0,0}, b={0,1}, c={1,1}
vector<int> Mark(int N, int M, int A, int B,vector<int> U, vector<int> V)
{
n=N;
m=M;
for(int i=0;i<m;i++)
{
int a=U[i],b=V[i];
muchii[a].push_back(b);
muchii[b].push_back(a);
g.push_back({a,b});
myind[{a,b}]=myind[{b,a}]=i;
}
bfs();
if(B==0)
{
vector<int> sol=subtask14();
return sol;
}
par[0]=-1;
sol.resize(m);
dfs(0);
return sol;
}
#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
namespace
{
bool penal;
int sure, prv;
pii aa={0,0},bb={0,1},cc={1,1};
vector<vector<pii>> bad={{aa,bb,cc},{cc,bb,bb},{bb,bb,bb,aa},{bb,bb,aa,bb},{bb,aa,bb,cc},{bb,cc,bb,bb}};
vector<pii> v;
pii gettype(vector<int> y)
{
if(y[0]==2)
return aa;
if(y[1]==2)
return cc;
return bb;
}
}
void Init(int A, int B)
{
if(B==0)
penal=1;
prv=-1;
sure=0;
}
int Move(vector<int> y)
{
if(penal)
{
int cnt=0;
for(int i=0;i<3;i++)
if(y[i]!=0)
cnt++;
if(cnt==1)
{
for(int i=0;i<3;i++)
if(y[i]>0)
return i;
}
if(y[0]>0&&y[1]>0)
return 0;
if(y[0]>0&&y[2]>0)
return 2;
return 1;
}
if(prv==-1)
{
if(y[0]+y[1]!=2)
{
sure=1;
if(y[0]==1)
{
prv=0;
return 0;
}
else
{
prv=1;
return 1;
}
}
pii x=gettype(y);
v.push_back(x);
prv=x.first;
return x.first;
}
if(sure==0)
{
if(y[0]+y[1]>=2)
{
sure=1;
y[prv]++;
if(y[prv]==1)
return -1;
else
{
prv=1-prv;
return prv;
}
}
if(y[0]+y[1]==0)
{
sure=1;
return -1;
}
y[prv]++;
pii x=gettype(y);
v.push_back(x);
for(auto j:bad)
{
if(j==v)
{
sure=1;
return -1;
}
}
y[prv]--;
if(v.size()>=4)
sure=1;
if(y[0]>=1)
{
prv=0;
return 0;
}
if(y[1]>=1)
{
prv=1;
return 1;
}
}
if(sure==1)
{
if(y[0]>=1&&y[1]>=1)
{
int cul=1-prv;
prv=cul;
return cul;
}
if(y[0]>=1)
{
prv=0;
return 0;
}
if(y[1]>=1)
{
prv=1;
return 1;
}
}
}
