#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, ch;
queue<array<int, 3> > qu;
vector<int> vis, p, pedg, dep;
std::vector<int> X;
vector<vector<int> > COLS = { {2, 0}, {0, 2}, {1, 1} };
void dfs5(int node, int col) {
if(node) X[pedg[node]] = col;
col++;
col %= 3;
for(auto c : ch[node]) {
dfs5(c[0], col);
}
}
int get_col(int x) {
if((int)ch[x].size() != 1) return 0;
vector<int> cnt(2, 0);
cnt[X[ch[x][0][1]]]++;
cnt[X[pedg[x]]]++;
for(int i = 0; i < 3; i++) {
if(cnt == COLS[i]) return i;
}
assert(0);
}
void dfs(int node) {
if(node && ch[node].size() == 1) {
int col = get_col(p[node]);
col++;
col %= 3;
auto tmp = COLS[col];
tmp[X[pedg[node]]]--;
for(int i = 0; i < 2; i++) {
if(tmp[i]) {
X[ch[node][0][1]] = i;
}
}
dfs(ch[node][0][0]);
}
else {
for(auto c : ch[node]) {
X[c[1]] = !X[pedg[node]];
if(!node) X[c[1]] = 0;
dfs(c[0]);
}
}
}
} // 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]});
}
if(B == 0) {
dfs5(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;
}
}
}
else {
dfs(0);
}
// cout << "edges: \n";
// for(auto c : X) {
// cout << c << " ";
// }
// cout << "\n";
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 {
vector<vector<int> > COLS = { {2, 0}, {0, 2}, {1, 1} };
int A, B;
int cur_edg = -1;
int prev_col = -1;
bool f = 0;
bool turn = 0;
int beg = 0;
void move_to(int x) {
// cout << "move: " << beg << " moved to:" << x << endl;
beg++;
if(x == -1) return;
turn = !x;
cur_edg = x;
return;
}
int get_col(vector<int> a) {
for(int i = 0; i < 3; i++) {
if(a == COLS[i]) return i;
}
assert(0);
}
} // namespace
void Init(int A, int B) {
cur_edg = -1;
beg = 0;
prev_col = -1;
f = 0;
turn = 0;
::A = A;
::B = B;
}
int Move(std::vector<int> y) {
if(B == 0) {
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);
}
else {
int sum = y[0] + y[1];
if(beg) {
sum++;
}
if(f) {
move_to(turn);
return !turn;
}
if(sum == 1) {
f = 1;
if(!beg) {
move_to(y[1] == 1);
return y[1] == 1;
}
else {
move_to(-1);
return -1;
}
}
if(sum > 2) {
f = 1;
if(beg) y[cur_edg]++;
if(y[cur_edg] == 1) {
move_to(-1);
return -1;
}
else if(y[0] == 1) {
move_to(0);
return 0;
}
else {
move_to(1);
return 1;
}
}
if(!beg) {
prev_col = get_col(y);
if(y[0]) {
move_to(0); return 0;
}
else {
move_to(1); return 1;
}
}
else if(beg == 1) {
int col = get_col(y);
f = 1;
if((col + 1) % 3 == prev_col) {
move_to(y[1] == 1);
return y[1] == 1;
}
else {
move_to(-1);
return -1;
}
}
assert(0);
}
}
