#include "Anthony.h"
#include <vector>
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
namespace {
const int NMAX = 3e4+5;
vector<vector<array<int, 2> > > adj(NMAX, vector<array<int, 2> >()), ch;
queue<array<int, 3> > qu;
vector<int> vis, p, pedg, dep;
std::vector<int> X;
void dfs(int node, int col) {
if(node) X[pedg[node]] = col;
col++;
col %= 3;
for(auto c : ch[node]) {
dfs(c[0], col);
}
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V) {
X.assign(M, -1);
vis.assign(N + 5, 0);
p.assign(N + 5, 0);
dep.assign(N + 5, 0);
pedg.assign(N + 5, 0);
while(qu.size()) qu.pop();
ch.assign(N + 5, vector<array<int, 2> >());
adj.assign(N + 5, vector<array<int, 2> >());
for(int i = 0; i < M; i++) {
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
qu.push({0, 0, 0});
dep[0] = 0;
while(qu.size()) {
auto cur = qu.front();
qu.pop();
if(vis[cur[0]]) continue;
vis[cur[0]] = 1;
p[cur[0]] = cur[1];
dep[cur[0]] = dep[cur[1]] + 1;
pedg[cur[0]] = cur[2];
for(auto c : adj[cur[0]]) {
if(vis[c[0]]) continue;
qu.push({c[0], cur[0], c[1]});
}
}
for(int i = 1; i < N; i++) {
ch[p[i]].pb({i, pedg[i]});
}
dfs(0, 0);
for(int i = 0; i < M; i++) {
if(X[i] != -1) continue;
if(dep[U[i]] < dep[V[i]]) swap(U[i], V[i]);
X[i] = X[pedg[U[i]]];
if(dep[U[i]] == dep[V[i]]) {
X[i]++;
X[i] %= 3;
}
}
return X;
}
#include "Catherine.h"
#include <vector>
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
namespace {
int A, B;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(std::vector<int> y) {
for(int i = 0; i < 3; i++) {
int nxt = i + 1;
nxt %= 3;
if(y[nxt] && y[i]) {
return i;
}
}
for(int i = 0; i < 3; i++) {
if(y[i]) return i;
}
assert(0);
}
