#include "Anthony.h"
#include <bits/stdc++.h>
#define debug //printf
#define pii pair<int,int>
#define ff first
#define ss second
#define mk make_pair
#define sz(x) (int)(x.size() )
#define ll long long
#define all(x) x.begin(),x.end()
const int MAXN = 2e4+10 ;
using namespace std ;
vector<pii> adj[MAXN] ;
int marcas[MAXN] , dist[MAXN] ;
int seq[6] = {0,1,0,0,1,1} ;
void dfs(int x, int father , int curIdx , int dist = 1 ) //curIdx eh o que eu tenho que colocar nas minhas proximas arestas
{
if( sz(adj[x]) != 2 ) curIdx = !seq[curIdx] ;
else curIdx = (curIdx == 5) ? 0 : (curIdx+1) ;
for(auto e : adj[x] )
{
if(e.ff == father ) continue ;
marcas[e.ss] = seq[curIdx] ;
dfs(e.ff, x, curIdx , dist+1 ) ;
}
}
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V)
{
for(int i = 0 ; i < M ; i++ )
{
adj[ U[i] ].push_back(mk(V[i] , i ) ) ;
adj[ V[i] ].push_back( mk(U[i],i) ) ;
}
if(A >= 3 )
{
//Constroi a arvore da bfs
for(int i = 1 ; i < N ; i++ ) dist[i] = -1 ;
vector<int> fila ;
int ini = 0 ;
fila.push_back(0) ;
while(ini < sz(fila) )
{
int x = fila[ini++] ;
for(auto e : adj[x] )
{
if(dist[e.ff] != -1 ) continue ;
fila.push_back(e.ff) ;
dist[e.ff] = dist[x] + 1 ;
}
}
for(int i = 0 ; i < M ; i++ )
{
int a = U[i] ;
int b = V[i] ;
if( dist[a] == dist[b] ) marcas[i] = dist[a] % 3 ;
else marcas[i] = min(dist[a] , dist[b] ) % 3 ;
}
}
else
{
for(auto neigh : adj[0] )
{
marcas[neigh.ss] = 0 ;
dfs(neigh.ff, 0, 0 ) ;
}
}
for(int i = 0 ; i < M ; i++ ) debug("Pintei %d %d de %d\n", U[i] , V[i] , marcas[i] ) ;
vector<int> answer(M,0) ;
for(int i = 0 ; i < M; i++ ) answer[i] = marcas[i] ;
return answer ;
}
#include "Catherine.h"
#include <bits/stdc++.h>
#define debug //printf
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
using namespace std ;
set< string > reversedOrder ;
bool is3 ;
void Init(int A, int B)
{
string seq = "010011" ;
if(A >= 3 ) is3 = true ;
//Creating reversedOrder
for(int i = 0 ,ant = 5 ; i < 6 ; i++ , ant++ )
{
if(ant == 6 ) ant = 0 ;
string str ;
for(int j = i; j != ant ; j = (j == 5 ) ? 0 : (j+1) )
str.push_back(seq[j] ) ;
reversedOrder.insert(str) ;
}
}
bool justGo , isFirst = true ;
int wentBefore ;
string str ;
int Move(vector<int> y)
{
if(is3)
{
int qtdNeigh = (y[0] > 0 ) + (y[1] > 0 ) + (y[2] > 0 ) ;
if(qtdNeigh == 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[1] > 0 && y[2] > 0 ) return 1 ;
if(y[2] >0 && y[0] > 0 ) return 2 ;
}
debug("meu vetor ta %d %d e justGo eh %d\n", y[0] , y[1] , justGo) ;
int qtdNeigh = y[0] + y[1] ;
if(qtdNeigh == 0)
{
justGo = true ;
return -1 ;
}
if(isFirst)
{
isFirst = false ;
if(qtdNeigh == 1 )
{
wentBefore = (y[0] == 1 ) ? 0 : 1 ;
justGo = true ;
return wentBefore ;
}
if(qtdNeigh == 2 )
{
if( y[0] && y[1] )
{
str.push_back('0') ;
str.push_back('1') ;
wentBefore = 1 ;
return 1 ;
}
int idx = (y[0] > y[1] ) ? 0 : 1 ;
str.push_back('0' + idx ) ;
str.push_back('0' + idx ) ;
wentBefore = idx ;
return idx ;
}
wentBefore = (y[0] < y[1] ) ? 0 : 1 ;
justGo = true ;
return wentBefore ;
}
if(justGo)
{
if( qtdNeigh == 1 )
{
wentBefore = (y[0] > y[1] ) ? 0 : 1 ;
return wentBefore ;
}
wentBefore = !wentBefore ;
return wentBefore ;
}
if(qtdNeigh > 1 )
{
justGo = true ;
if(y[!wentBefore] != 1 ) return -1 ;
wentBefore = !wentBefore;
return wentBefore;
}
//Ainda estou presa na corrente
str.push_back( '0' + ( (y[0] == 1) ? 0 : 1 ) ) ;
if(sz(str) == 5 )
{
justGo = true ;
if( reversedOrder.find(str) != reversedOrder.end() ) return -1 ;
else
{
wentBefore = (y[0] == 1 ) ? 0 : 1 ;
return wentBefore ;
}
}
wentBefore = (y[0] == 1 ) ? 0 : 1 ;
return wentBefore ;
}
