#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
vector<ii> vec;
vector<ii> back;
struct Graph
{
struct edge
{
int v; ll weight;
};
vector<vector<edge> > adj;
int n;
Graph(int _n)
{
adj.resize(_n);
n = _n;
}
void addedge(int u, int v, ll c)
{
edge tmp;
tmp.v = v; tmp.weight = c;
adj[u].pb(tmp);
tmp.v = u;
adj[v].pb(tmp);
}
void reset()
{
adj.clear();
}
vector<ll> dist;
vi par;
void bfs(int s)
{
ll INFI = ll(1e18);
dist.assign(n, INFI);
par.assign(n, -1);
dist[s] = 0; par[s] = -1;
queue<int> q; q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i].v;
if(dist[v] >= INFI)
{
vec.pb({u,v});
dist[v] = dist[u] + 1;
par[v] = u;
q.push(v);
}
else
{
back.pb({u,v});
}
}
}
}
};
vi chain = {1,0,0,1,1,0};
int col[22222];
vi adj[22222];
int par[22222];
void dfs(int u, int p, int chainno=-1)
{
int child=0;
for(int v:adj[u])
{
if(v==p) continue;
par[v]=u;
child++;
}
if(child>=2)
{
for(int v:adj[u])
{
if(v==p) continue;
col[v]=col[u]^1;
dfs(v,u,-1);
}
}
else if(child==1)
{
for(int v:adj[u])
{
if(v==p) continue;
if(chainno>=0)
{
col[v] = chain[(chainno+1)%6];
dfs(v,u,(chainno+1)%6);
}
else
{
col[v]=col[u]^1;
if(col[v]==1) dfs(v,u,0);
else dfs(v,u,1);
}
}
}
}
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V)
{
std::vector<int> ans(M);
int n=N; int m=M;
Graph G(n);
map<ii,int> ma;
for(int i=0;i<m;i++)
{
G.addedge(U[i],V[i],1);
ma[{U[i],V[i]}]=ma[{V[i],U[i]}]=i;
adj[U[i]].pb(V[i]);
adj[V[i]].pb(U[i]);
}
G.bfs(0);
if(A>=3)
{
for(ii x:vec)
{
int ed = ma[x];
int mind = min(G.dist[x.fi],G.dist[x.se]);
ans[ed]=mind%3;
}
for(ii x:back)
{
int ed = ma[x];
int mind = min(G.dist[x.fi],G.dist[x.se]);
ans[ed]=mind%3;
}
return ans;
}
col[0]=0;
dfs(0,-1);
for(int i=1;i<n;i++)
{
ans[ma[{i,par[i]}]] = col[i];
}
return ans;
}
#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
namespace {
int A, B;
int beg = 0;
int up=0;
vi path;
vi chain = {1,0,0,1,1,0};
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
::beg = 0;
::up = 0;
::path.clear();
}
int Move(std::vector<int> y)
{
if(A>=3)
{
int S[3]={};
int mx=0;
for(int i=0;i<3;i++)
{
if(y[i]>0)
{
mx=i; S[i]=1;
}
}
if(S[0]+S[1]+S[2]==1) return mx;
if(S[0]&&S[1]) return 0;
if(S[1]&&S[2]) return 1;
return 2;
}
else
{
//rmb to check leaf case
//cerr<<y[0]<<' '<<y[1]<<'\n';
if(up) //if we are certain we are going up
{
if(y[0]+y[1]==1)
{
if(y[0]==1){path.pb(0); return 0;}
path.pb(1); return 1;
}
path.pb((path.back()^1));
return path.back();
}
if(!beg)
{
if(y[0]+y[1]==1)
{
up=1;
if(y[1]==1){path.pb(1); return 1;}
else{path.pb(0); return 0;}
}
if(y[0]+y[1]>2)
{
up=1;
if(y[0]==1){path.pb(0); return 0;}
if(y[1]==1){path.pb(1); return 1;}
assert(0);
}
if(y[0]>0)
{
y[0]--; path.pb(0);
}
else
{
y[1]--; path.pb(1);
}
if(y[0]>0) path.pb(0);
else path.pb(1);
reverse(path.begin(),path.end());
beg=1;
return path.back();
}
//got previous liao
if(y[0]+y[1]==0)
{
up=1;
return -1; //can go back
}
if(y[0]==0&&y[1]>1)
{
up=1;
path.pb(0);
return -1;
}
if(y[0]>1&&y[1]==0)
{
up=1;
path.pb(1);
return -1;
}
if(y[0]+y[1]>1)
{
up=1;
y[path.back()]++;
if(y[0]==1)
{
path.pb(0);
return 0;
}
if(y[1]==1)
{
path.pb(1);
return 1;
}
assert(0);
}
//chain now
//cerr<<y[0]<<' '<<y[1]<<' '<<path[0]<<' '<<path.back()<<' '<<path.size()<<' '<<up<<'\n';
if(path.size()>=4)
{
vi V;
for(int i=int(path.size())-4;i<int(path.size());i++)
{
V.pb(path[i]);
}
if(y[0]==1)
{
V.pb(0);
}
else
{
V.pb(1);
}
bool pos=0;
for(int i=0;i<6;i++)
{
vi v2;
for(int j=i;j<i+5;j++)
{
v2.pb(chain[j%6]);
}
if(v2==V){pos=1; break;}
}
if(pos)
{
up=1; return -1;
}
else up=1;
}
if(y[0]==1)
{
path.pb(0); return 0;
}
if(y[1]==1)
{
path.pb(1); return 1;
}
assert(0);
}
}
