#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 2e4;
static int N, M, A, B, D[MAXN+10];
static pii E[MAXN+10];
static vector<pii> adj[MAXN+10];
static vector<int> ret;
static int S[10]={1, 1, 0, 1, 0, 0};
void dfs(int now, int bef, int col, int cnt)
{
int chd=0;
if(now==bef) chd=adj[now].size();
else chd=adj[now].size()-1;
if(chd>=2)
{
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
ret[nxt.second-1]=1-col;
dfs(nxt.first, now, 1-col, 1-col);
}
}
else if(chd==1)
{
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
ret[nxt.second-1]=S[cnt];
dfs(nxt.first, now, S[cnt], (cnt+1)%6);
}
}
}
vector<int> Mark(int _N, int _M, int _A, int _B, vector<int> _U, vector<int> _V)
{
N=_N; M=_M; A=_A; B=_B;
for(int i=1; i<=M; i++)
{
int u=_U[i-1]+1, v=_V[i-1]+1;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
E[i]={u, v};
}
ret.resize(M);
if(B==0)
{
queue<int> Q;
memset(D, -1, sizeof(D));
Q.push(1); D[1]=0;
while(!Q.empty())
{
int now=Q.front(); Q.pop();
for(auto nxt : adj[now])
{
if(D[nxt.first]!=-1) continue;
Q.push(nxt.first);
D[nxt.first]=D[now]+1;
}
}
for(int i=1; i<=M; i++) ret[i-1]=min(D[E[i].first], D[E[i].second])%3;
return ret;
}
dfs(1, 1, 1, 0);
return ret;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 2e4;
static int A, B;
static vector<int> V;
string S;
static int cnt, bef;
static bool up;
vector<string> VV = {"11010", "10100", "10011", "00110", "01101"};
void Init(int _A, int _B)
{
A=_A; B=_B;
cnt=0; up=false;
}
int Move(vector<int> _V)
{
V=_V;
cnt++;
if(B==0)
{
if(V[0]==0 && V[1]==0) return 2;
if(V[0]==0 && V[2]==0) return 1;
if(V[2]==0 && V[1]==0) return 0;
if(V[0]==0) return 1;
if(V[1]==0) return 2;
if(V[2]==0) return 0;
}
int deg=0;
deg=V[0]+V[1];
if(cnt!=1) deg++;
if(cnt==1)
{
if(V[0]==1 && V[1]==0) { up=true; return bef=0; }
if(V[0]==0 && V[1]==1) { up=true; return bef=1; }
if(deg>=3)
{
up=true;
if(V[0]==1) { return bef=0; }
if(V[1]==1) { return bef=1; }
}
assert(deg==2);
if(V[1]==2) { S.push_back('1'); S.push_back('1'); return bef=1; }
if(V[0]==2) { S.push_back('0'); S.push_back('0'); return bef=0; }
if(V[0]==1 && V[1]==1) { S.push_back('1'); S.push_back('0'); return bef=0; }
}
else
{
if(deg>=3)
{
up=true;
if(V[0]==0) { return -1; }
if(V[1]==0) { return -1; }
bef=!bef;
return bef;
}
if(deg==1)
{
up=true;
return -1;
}
if(up)
{
if(V[1]==1) return bef=1;
if(V[0]==1) return bef=0;
}
if(cnt<4)
{
if(V[1]==1) { S.push_back('1'); return bef=1; }
if(V[0]==1) { S.push_back('0'); return bef=0; }
}
if(V[1]==1) S.push_back('1');
else if(V[0]==1) S.push_back('0');
bool flag=false;
for(auto it : VV) if(it==S) flag=true;
up=true;
if(flag) return -1;
else
{
if(V[1]==1) return bef=1;
if(V[0]==1) return bef=0;
}
}
}
