#include "Anthony.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define trav(x, a) for (const auto& x: a)
#define sz(x) (int)(x).size()
#define pb push_back
using namespace std;
namespace {
const int N = 2e4 + 5;
vi adj[N];
int dp[N];
string bl = "001011";
}
vi Mark(int N, int M, int A, int B, vi U, vi V) {
// const int ln = 6;
// for (int i = 0; i < (1<<ln); i++) {
// string cur, xcur;
// for (int j = ln-1; ~j; j--) {
// cur.pb((char)('0'+((i >> j) & 1)));
// xcur.pb(cur.back()^1);
// }
// string tmp = cur + cur;
// int ok = tmp.find(cur, 1) != string::npos;
// int o = tmp.find(xcur) != string::npos;
// reverse(tmp.begin(), tmp.end());
// ok &= ok ^ (tmp.find(cur) != string::npos);
// o &= tmp.find(xcur) == string::npos;
// if (ok) {
// cerr << cur << " " << xcur << endl;
// }
// }
for (int i = 0; i < M; i++)
adj[U[i]].pb(i), adj[V[i]].pb(i);
if (A > 2) {
deque<int> pq;
pq.pb(0);
fill(dp, dp+N, N+1);
dp[0] = 0;
vi X(M);
for (int i = 0; i < M; i++)
X[i] = 2;
while (!pq.empty()) {
int u = pq.front(); pq.pop_front();
trav(x, adj[u]) {
int v = U[x]^V[x]^u;
if (dp[v] > dp[u] + 1) {
dp[v] = dp[u] + 1;
pq.pb(v);
}
if (dp[v] == dp[u] + 1 || dp[v] == dp[u]) {
X[x] = dp[u]%3;
}
}
}
return X;
}
vi X(M);
function<void(int,int,int,int)> dfs = [&](int u, int p, int d, int l) {
int f = (u != 0 && sz(adj[u]) > 2 ? 1 : 0);
// cerr << u << " " << f << " " << l << endl;
trav(x, adj[u]) {
int v = U[x]^V[x]^u;
if (v != p) {
X[x] = f ? l : bl[d%sz(bl)]-'0';
dfs(v, u, d+(f?0:1), X[x]^1);
}
}
};
dfs(0, -1, 0, 0);
// for (int i = 0; i < M; i++)
// cerr << U[i] << " " << V[i] << " / " << X[i] << endl;
return X;
}
#include "Catherine.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define sz(x) (int)(x).size()
#define pb push_back
using namespace std;
int A, B;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get(int l, int r) {
return uniform_int_distribution<int>(l,r)(rng);
}
void Init(int A, int B) {
::A = A;
::B = B;
}
namespace {
int lst = -1;
bool fnd = 0;
string bl = "001011001011";
string rbl = "110100110100";
string cur = "";
}
int Move(vi y) {
if (A > 2) {
if (~lst) y[lst]++;
if (y[0] && y[1])
return lst = 0;
if (y[0] && y[2])
return lst = 2;
if (y[1] && y[2])
return lst = 1;
for (int i = 0; i < 3; i++)
if (y[i])
return lst = i;
}
if (fnd) {
if (y[0]+y[1] > 1)
y[lst]++;
return lst = (y[0]==1 ? 0 : 1);
}
if (lst == -1) {
if (y[0]+y[1] == 1) {
fnd = 1;
return lst = (y[0]==1 ? 0 : 1);
}
if (y[0]+y[1] > 2) {
fnd = 1;
return lst = (y[0]==1 ? 0 : 1);
}
lst = (y[0]>0 ? 0 : 1);
cur.pb((char)('0'+lst));
return lst;
}
if (y[0]+y[1]==0) {
fnd = 1;
return -1;
}
if (y[0]+y[1]>1) {
fnd = 1;
y[lst]++;
if (y[lst] == 1)
return -1;
return lst = lst^1;
}
vector<int> pos;
for (int i = 0; i < 6; i++) {
bool fl = 1;
for (int j = 0; fl && j < sz(cur); j++)
fl &= cur[j] == bl[i+j];
if (fl)
pos.pb(i);
fl = 1;
for (int j = 0; fl && j < sz(cur); j++)
fl &= cur[j] == rbl[i+j];
if (fl)
pos.pb(~i);
}
if (sz(pos) == 1) {
// cerr << "found dir: " << pos[0] << "\n";
fnd = 1;
if (pos[0] >= 0)
return -1;
return lst = (y[0]==1 ? 0 : 1);
}
lst = (y[0]==1 ? 0 : 1);
cur.pb((char)('0'+lst));
return lst;
}
