#include <bits/stdc++.h>
#include "Anthony.h"
using namespace std;
#define pii pair<int, int>
#define F first
#define S second
static const int maxn = 2e4 + 10;
static int n, m, a, b,
seq[] = {0, 1, 0, 1, 1, 0},
dist[maxn];
static vector<pii> adj[maxn];
static vector<int> x;
void mark1(){
fill(dist, dist + n, -1);
queue<int> q; // {{node, par}, last colour}
q.push(0); dist[0] = 0;
while (!q.empty()){
int v = q.front(); q.pop();
for (auto k : adj[v]){
int u = k.F, i = k.S;
if (dist[u] != -1) continue;
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
void mark2(int v, int p, int last_idx){
int cnt_children = 0, next_idx;
for (auto k : adj[v]){
int u = k.F, i = k.S;
if (u != p) cnt_children++;
}
if (cnt_children <= 1){ // line
next_idx = (last_idx == 5 ? 0 : last_idx + 1);
}
else{ // multiple children
next_idx = (seq[last_idx] == 0 ? 1 : 0);
}
for (auto k : adj[v]){
int u = k.F, i = k.S;
if (u == p) continue;
x[i] = seq[next_idx];
mark2(u, v, next_idx);
}
}
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;
x.resize(m, -1);
for (int i = 0; i < m; i++){
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
if (a >= 3){ // type 1: bfs tree; 2 -> 1 -> 0
mark1();
for (int v = 0; v < n; v++){
for (auto k : adj[v]){
int u = k.F, i = k.S;
if (dist[u] < dist[v]) x[i] = dist[u] % 3;
else x[i] = dist[v] % 3;
}
}
// for (int v = 0; v < n; v++){
// cout << v << ": dist = " << dist[v] << endl;
// for (auto k : adj[v]){
// cout << "to " << k.F << ": " << x[k.S] << endl;
// }
// cout << endl;
// cout << endl;
// }
}
else{
mark2(0, 0, 0);
}
return x;
}
#include <bits/stdc++.h>
#include "Catherine.h"
using namespace std;
#define pii pair<int, int>
#define F first
#define S second
static const int maxn = 2e4 + 10;
static int n, m, a, b, last = -1,
seq[] = {0, 1, 0, 1, 1, 0};
static bool is_type_1;
void Init(int A, int B){
a = A, b = B;
if (a >= 3) is_type_1 = true;
else is_type_1 = false;
}
int Move(vector<int> y){
if (is_type_1){
// for (auto k : y) cout << k << ' '; cout << endl;
for (int i = 0; i < a; i++){
int next = (i == 0 ? 2 : i - 1);
if (y[i] > 0 && y[next] == 0) return i;
}
}
else{
cout << 'b';
return -1;
}
return -1;
}
