#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} };
vector<vector<int> > ord;
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);
}
int ind = 0, typ = -1;
void dfs(int node) {
// cout << "node: " << node << endl;
if(node && ch[node].size() == 1) {
if(typ == -1) {
ind = 2; typ = X[pedg[node]];
X[ch[node][0][1]] = ord[typ][1];
dfs(ch[node][0][0]);
}
else {
ind++; ind %= 6;
X[ch[node][0][1]] = ord[typ][ind];
dfs(ch[node][0][0]);
}
}
else {
// cout << "node? : " << node << endl;
typ = -1;
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);
ord = { {0, 0, 1, 1, 0, 1}, {1, 1, 0, 1, 0, 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]});
}
// for(int i = 0; i < N; i++) {
// cout << "i: " << i << endl;
// cout << "ch: ";
// for(auto c : ch[i]) cout << c[0] << " ";
// cout << endl;
// }
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 << "dfs donde" << endl;
}
// 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;
vector<int> cols;
bool f = 0;
bool turn = 0;
int beg = 0;
void move_to(int x) {
// cout << "move: " << beg << " moved to:" << x << endl;
beg++;
turn = !cur_edg;
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;
cols.clear();
f = 0;
turn = 0;
::A = A;
::B = B;
}
int Move(std::vector<int> y) {
if(B == 0) {
assert(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) {
if(sum == 2) {
move_to(y[1] == 1);
return y[1] == 1;
}
y[cur_edg]++;
assert(y[cur_edg] != 1);
move_to(y[1] == 1);
return y[1] == 1;
}
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(beg && 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) {
cols.pb(get_col(y));
move_to(y[1] >= 1);
return y[1] >= 1;
}
else if(beg < 3) {
y[cur_edg]++;
cols.pb(get_col(y));
y[cur_edg]--;
move_to(y[1] == 1);
return y[1] == 1;
}
else {
f = 1;
y[cur_edg]++;
int cur = get_col(y);
y[cur_edg]--;
cols.pb(cur);
int par = 0;
for(int i = 0; i < cols.size(); i++) {
if(cols[i] != 2) {
par = i % 2;
}
}
if((cols[2 + par] + 1) % 3 == cols[par]) {
move_to(y[1] == 1);
return y[1] == 1;
}
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) {
// // cout << "here" << endl;
// y[cur_edg]++;
// int col = get_col(y);
// y[cur_edg]--;
// 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);
}
}
