#include "Anthony.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
namespace {
const int N = 20'010;
vector<int> A[N];
int dis[N];
void bfs() {
memset(dis, -1, sizeof(dis));
vector<int> q = {0};
dis[0] = 0;
Loop (i,0,q.size()) {
int v = q[i];
for (int u : A[v]) {
if (dis[u] == -1) {
dis[u] = dis[v]+1;
q.push_back(u);
}
}
}
}
int height[N];
int val[N];
const int pat[] = {0, 0, 1, 0, 1, 1};
const int pats = sizeof(pat)/sizeof(*pat);
void dfs(int v, int p, int x, int h) {
height[v] = h;
val[v] = pat[x%pats];
for (int u : A[v]) {
if (u == p)
continue;
if (A[v].size() == 2)
dfs(u, v, x+1, h+1);
else
dfs(u, v, val[v]==0? 2: 0, h+1);
}
}
} // namespace
std::vector<int> Mark(int N, int M, int a, int b,
std::vector<int> U, std::vector<int> V) {
Loop (i,0,M) {
int v = V[i], u = U[i];
A[v].push_back(u);
A[u].push_back(v);
}
vector<int> ans(M);
if (a == 2) {
dfs(0, -1, 0, 0);
Loop (i,0,M) {
int v = V[i], u = U[i];
if (height[v] > height[u])
swap(v, u);
ans[i] = val[u];
}
} else {
bfs();
Loop (i,0,M) {
int v = V[i], u = U[i];
ans[i] = min(dis[v], dis[u]) % 3;
}
}
return ans;
}
#include "Catherine.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
namespace {
int (*move_ptr)(vector<int>);
int lst = -1;
int move3(vector<int> y) {
if (y[0] && y[1])
return 0;
if (y[1] && y[2])
return 1;
if (y[2] && y[0])
return 2;
return !!y[1] + 2*!!y[2];
}
int move_up(vector<int> y) {
if (!!y[0] + !!y[1] == 1)
return !!y[1];
if (y[0] + (lst == 0) == 1)
return 0;
else
return 1;
}
const int pat[] = {0, 0, 1, 0, 1, 1};
const int pats = sizeof(pat)/sizeof(*pat);
vector<int> cur_pat;
bool test() {
vector<int> p(pat, pat+pats), q(cur_pat);
Loop (_,0,pats) {
int x = p.back();
p.pop_back();
if (p == q)
return 0;
p.insert(p.begin(), x);
}
return 1;
}
int move_test(vector<int> y) {
if (y[0] + y[1] + (lst != -1) != 2)
return (move_ptr = move_up)(y);
if (cur_pat.size() == 0) {
if (y[0] && y[1]) {
cur_pat = {0, 1};
return 1;
}
if (y[0]) {
cur_pat = {0, 0};
return 0;
} else {
cur_pat = {1, 1};
return 1;
}
}
cur_pat.push_back(!!y[1]);
if (cur_pat.size() == 5) {
move_ptr = move_up;
if (test())
return move_up(y);
else
return -1;
}
return !!y[1];
}
} // namespace
void Init(int A, int B) {
move_ptr = A == 2? move_test: move3;
}
int Move(std::vector<int> y) {
int x = move_ptr(y);
lst = x;
return x;
}
