#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;
// 0 -> 1 -> 2
vi Mark(int n, int m, int a, int b, vi U, vi V) {
vector<vi> g(n);
auto cp = [&](int u, int v) -> pi {
if (u > v) swap(u, v);
return mp(u, v);
};
map<pi, int> conv;
vpi ed;
vi res(m);
f0r(i, m) {
int u = U[i];
int v = V[i];
assert(u < n);
assert(v < n);
conv[cp(u, v)] = i;
g[u].pb(v);
g[v].pb(u);
ed.pb(cp(u, v));
}
if (a >= 3) { // bfs work
vi dist(n, -1);
list<int> que;
dist[0] = 0;
que.pb(0);
while (!que.empty()) {
int u = que.front();
que.pop_front();
each(v, g[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
que.push_back(v);
}
}
each(e, ed) {
int u = e.f;
int v = e.s;
int id = conv[cp(u, v)];
if (dist[u] == dist[v]) {
res[id] = dist[u] % 3;
} else {
if (dist[u] > dist[v]) {
swap(u, v);
}
res[id] = dist[u] % 3;
}
}
} else {
assert(n - 1 == m);
vi par(n);
int cnt = 0;
function<void(int, int)> dfs_precomp = [&](int u, int p) {
assert(u < n);
par[u] = p;
each(v, g[u]) {
if (v == p) continue;
dfs_precomp(v, u);
}
};
dfs_precomp(0, -1);
vi lab(n);
function<void(int, int, int)> dfs_label = [&](int u, int p, int d) {
if (u == 0) {
each(v, g[u]) {
if (v == p) continue;
lab[v] = 0;
dfs_label(v, u, 0);
}
return;
}
if (sz(g[u]) == 1) return;
if (sz(g[u]) > 2) {
each(v, g[u]) {
if (v == p) continue;
lab[v] = lab[u] ^ 1;
dfs_label(v, u, 0);
}
} else {
each(v, g[u]) {
if (v == p) continue;
if (d == 0 || d == 2 || d == 5) {
lab[v] = lab[u] ^ 1;
} else {
lab[v] = lab[u];
}
dfs_label(v, u, (d + 1) % 6);
}
}
};
dfs_label(0, -1, -1);
f1r(i, 1, n) {
int id = conv[cp(i, par[i])];
res[id] = lab[i];
}
}
return res;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;
namespace {
int a, b;
vi moves;
vpi seen;
bool oriented = false;
} // namespace
void Init(int A, int B) {
::a = A;
::b = B;
}
int MoveT(vi& v) {
// cout << "MOVE" << endl;
int x = v[0];
int y = v[1];
pi use = {x, y};
if (sz(moves)) {
if (moves.back() == 0) use.f++;
else use.s++;
}
seen.pb(use);
#define R(k) moves.pb(k); return k;
#define F() if (x) { R(0); } else { R(1); }
// R is for moving to a color
// F is if you're on a line, move forward
if (oriented) { // if you're already oriented
assert(x || y);
if (x == 0) {
R(1);
} else if (y == 0) {
R(0);
}
if (sz(moves)) {
if (moves.back() == 0) x++;
else y++;
}
if (x > y) {
assert(y == 1);
R(1);
} else if (x < y) {
assert(x == 1);
R(0);
}
assert(false);
R(-1); // shouldn't reach here
}
{ // checking if you're already at a good place
if (x == 0 && y == 0) { // dead end leaf node
oriented = true;
R(-1);
}
if (sz(moves)) {
if (moves.back() == 0) x++;
else y++;
}
if (x == 0 && y == 1) { // leaf nodes
oriented = true;
R(1);
} else if (y == 0 && x == 1) {
oriented = true;
R(0);
}
if (x > y && y) { // you already reached a good place
oriented = true;
assert(y == 1);
if (sz(moves)) {
if (moves.back() == 0) x--;
else y--;
}
if (y == 0) {
R(-1);
}
else {
R(1);
}
} else if (x < y && x) {
oriented = true;
assert(x == 1);
if (sz(moves)) {
if (moves.back() == 0) x--;
else y--;
}
if (x == 0) {
R(-1);
} else {
R(0);
}
}
if (sz(moves)) {
if (moves.back() == 0) x--;
else y--;
}
}
// each(x, moves) cout << x << " ";
// cout << endl;
// each(x, seen) cout << "(" << x.f << ", " << x.s << ") ";
// cout << endl;
int did = sz(moves);
if (did == 0) { // first move
F();
} else if (did == 1) {
if (seen[0].f == seen[0].s) { // 0 1, went 0 before
if (x) { // go 0 if possible
R(0);
} else {
R(-1);
}
} else { // same things
if (moves.back() == 0 && x) {
R(-1);
} else if (moves.back() == 1 && y) {
R(-1);
} else {
F();
}
}
} else if (did == 2) {
if (moves.back() == -1) {
F();
} else {
R(-1);
}
} else if (did == 3) {
F();
} else if (did == 4) {
if (moves[2] == -1) {
F();
} else {
R(-1);
}
} else if (did == 5) {
if (moves.back() == -1) {
F();
} else {
R(-1);
}
} else if (did == 6) {
oriented = true;
vi came; // direction just came from
vi other; // other direction
{ // came
if (moves[4] == -1 && moves[5] != -1) {
came.pb(moves[2]);
came.pb(moves[3]);
if (seen[4].f >= 2) {
came.pb(0);
} else if (seen[4].s >= 2) {
came.pb(1);
} else {
came.pb(came.back() ^ 1);
}
} else {
came.pb(moves[4]);
if (seen[5].f >= 2) {
came.pb(0);
} else if (seen[5].s >= 2) {
came.pb(1);
} else {
came.pb(came.back() ^ 1);
}
}
}
{ // other
if (moves[0] != -1 && moves[1] != -1) {
other.pb(moves[0]);
other.pb(moves[1]);
if (seen[2].f >= 2) {
other.pb(0);
} else if (seen[2].s >= 2) {
other.pb(1);
} else {
other.pb(other.back() ^ 1);
}
} else {
other.pb(moves[0]);
if (seen[1].f >= 2) {
other.pb(0);
} else if (seen[1].s >= 2) {
other.pb(1);
} else {
other.pb(other.back() ^ 1);
}
}
}
vi comb = came;
reverse(all(comb));
each(x, other) comb.pb(x);
// cout << "COMB" << endl;
// each(x, comb) cout << x << " ";
// cout << endl;
vi use;
int i1 = 0;
int i2 = 0;
int sz = sz(comb);
while (i1 != sz) {
while (i2 < sz - 1 && comb[i2 + 1] == comb[i2]) ++i2;
use.pb(i2 - i1 + 1);
i1 = ++i2;
}
int num = 0;
each(x, use) num += x;
assert(num == 5);
if (sz(use) == 2) {
int u = use[0];
int v = use[1];
if (u == 2) {
R(-1);
} else {
F();
}
} else if (sz(use) == 3) {
int u = use[0];
int v = use[1];
int w = use[2];
if (u == 1) {
if (v == 2) {
R(-1);
} else if (v == 1) {
F();
} else {
assert(false);
}
} else if (u == 2) {
if (v == 2) {
F();
} else {
assert(false);
}
} else if (u == 3) {
R(-1);
}
} else {
if (use[1] == 2) {
F();
} else {
R(-1);
}
}
} else {
assert(false);
}
// cout << did << endl;
// cout << "YA" << endl;
assert(false);
R(-1);
}
int MoveG(vi& y) {
int a0 = y[0];
int a1 = y[1];
int a2 = y[2];
if (a0 && a1) {
return 0;
} else if (a1 && a2) {
return 1;
} else if (a2 && a0) {
return 2;
} else if (a0) {
return 0;
} else if (a1) {
return 1;
} else if (a2) {
return 2;
}
return -1;
}
int Move(vi y) {
if (a >= 3) {
return MoveG(y);
} else {
return MoveT(y);
}
}
