#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;
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;
}
}
}
else{
mark2(0, 0, 0);
// for (int v = 0; v < n; v++){
// cout << v << endl;
// for (auto k : adj[v]){
// cout << "to " << k.F << ": " << x[k.S] << endl;
// }
// cout << endl;
// cout << endl;
// }
}
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, found_direction = false,
is_backtracking = false;
static vector<int> bruh;
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;
}
return -1;
}
else{
if (found_direction){
int cnt = y[0] + y[1] + 1, next;
if (cnt >= 3){ // not line
y[last]++;
next = (y[0] < y[1] ? 0 : 1);
}
else{ // is line
next = (y[0] == 0 ? 1 : 0);
}
last = next;
return next;
}
if (is_backtracking){
last = bruh.back(); bruh.pop_back();
if (bruh.empty()) found_direction = true;
return last;
}
else{
vector<int> x = y;
if (last != -1) x[last]++;
int cnt = y[0] + y[1], next;
if (cnt >= 3){ // not line
found_direction = true;
next = (y[0] < y[1] ? 0 : 1);
last = next;
return next;
}
else{
if (last == -1){ // first one
if (cnt == 1){
found_direction = true;
last = (y[0] ? 0 : 1);
}
else if (y[0] == 2){
bruh.push_back(0);
last = 0;
}
else if (y[0] == 1){
bruh.push_back(0);
last = 1;
}
else if (y[0] == 0){
bruh.push_back(1);
last = 1;
}
// cout << last << endl;
bruh.push_back(last);
return last;
}
else if (bruh.size() <= 3){
last = (y[0] ? 0 : 1);
bruh.push_back(last);
return last;
}
else{ // completed
bruh.push_back(y[0] ? 0 : 1);
bool is_right = false;
for (int start = 0; start < 6; start++){
bool pos = true;
for (int i = 0; i < 5; i++){
if (bruh[i] != seq[(start + i) % 6]) pos = false;
}
if (pos) is_right = true;
}
if (is_right){
found_direction = true;
last = bruh.back();
return last;
}
else{
is_backtracking = true;
last = bruh.back(); bruh.pop_back();
return -1;
}
}
}
}
}
return -1;
}
