#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int MAXN = 20005;
vector<pair<int, int>> adj[MAXN];
vector<int> marking;
int cyc[6] = {0, 0, 1, 0, 1, 1};
void dfs(int x, int par, int cind){
if (par != -1 && adj[x].size() >= 3){
int prv = cyc[(cind + 5) % 6];
if (prv == 0) cind = 5;
else cind = 0;
}
for (auto nxt : adj[x]){
int nn = nxt.first, edge = nxt.second;
if (nn == par) continue;
marking[edge] = cyc[cind];
dfs(nn, x, (cind + 1) % 6);
}
}
}
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({V[i], i});
adj[V[i]].push_back({U[i], i});
}
marking.resize(M);
if (A >= 3){
vector<int> dist(N, -1);
dist[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()){
int x = q.front(); q.pop();
for (auto nxt : adj[x]){
int nn = nxt.first, edge = nxt.second;
if (dist[nn] != -1){
if (dist[nn] == dist[x] - 1) continue; // already marked
else marking[edge] = dist[x] % 3;
}
else{
marking[edge] = dist[x] % 3;
dist[nn] = dist[x] + 1;
q.push(nn);
}
}
}
}
else{
dfs(0, -1, 0);
}
return marking;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B;
int steps = 0; // 0 to 3 -> first steps, -1 -> straight up
int prv = -1; // previous edge
int seq = 0; // 5 digit sequence
set<int> ok;
}
void Init(int A, int B) {
::A = A;
::B = B;
// up: 11010, 10100, 01001, 10011, 00110, 01101
ok = {26, 20, 9, 19, 6, 13};
}
int Move(vector<int> y){
if (A >= 3){
int types = 0;
for (int i = 0; i < 3; i++)
if (y[i])
types++;
if (types == 1){
for (int i = 0; i < 3; i++)
if (y[i])
return i;
}
else{ // types == 2
for (int i = 0; i < 3; i++)
if (!y[i])
return (i + 1) % 3;
}
return -1; // will never happen
}
else{
if (y[0] == 0 && y[1] == 0){ // dead end
steps = -1; // prv unchanged
return -1;
}
else if (y[0] + y[1] + (prv != -1) >= 3){ // deg >= 3
steps = -1;
int y0 = y[0] + (prv == 0), y1 = y[1] + (prv == 1);
if (y0 == 1){
int ret = ((prv == 0) ? -1 : 0);
prv = 0;
return ret;
}
else{
int ret = ((prv == 1) ? -1 : 1);
prv = 1;
return ret;
}
}
else if (steps == -1){ // go up
if (y[0]) return prv = 0;
else return prv = 1;
}
else if (steps == 0){
int go, other;
if (y[0]){
go = 0;
if (y[1]) other = 1; else other = 0;
}
else go = other = 1;
steps++;
prv = go;
seq = (other << 1) + go;
return go;
}
else if (steps < 3){
int go;
if (y[0]) go = 0; else go = 1;
steps++;
prv = go;
seq = (seq << 1) + go;
return go;
}
else{ // see if we are going correct direction
int nxt;
if (y[0]) nxt = 0; else nxt = 1;
seq = (seq << 1) + nxt;
steps = -1;
if (ok.count(seq)){ // continue
return prv = nxt;
}
else return -1;
}
}
}
