#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define MAX 101010
namespace {
vector<ll> adj[MAX], num[MAX], depth, deg, arr;
vector<ll> ret;
ll asdf[6] = { 1, 1, 0, 1, 0, 0 };
void dfs(ll x = 0, ll p = -1, ll d = 1, ll str = 0, ll chk = 0) {
depth[x] = d;
ll i;
for (i = 0; i < (int)adj[x].size(); i++) {
if (adj[x][i] == p) continue;
if (deg[adj[x][i]] == 2) {
if (!chk) {
while (d != asdf[str % 6]) str++;
}
ret[num[x][i]] = asdf[str % 6];
dfs(adj[x][i], x, !asdf[str % 6], str + 1, 1);
}
else {
ret[num[x][i]] = d;
dfs(adj[x][i], x, !d);
}
}
}
void bfs() {
queue<pair<ll, ll>> q;
q.push({ 0, 0 });
while (!q.empty()) {
pair<ll, ll> t;
t = q.front();
q.pop();
ll v = t.first;
if (arr[v] != -1) continue;
arr[v] = t.second;
for (auto x : adj[v]) {
q.push({ x, (t.second + 1) % 3 });
}
}
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
if (A != 2) {
ll i;
for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
for (i = 0; i < M; i++) num[U[i]].push_back(i);
for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
for (i = 0; i < M; i++) num[V[i]].push_back(i);
ret.resize(M);
arr.resize(N);
for (i = 0; i < M; i++) ret[i] = -1;
for (i = 0; i < N; i++) arr[i] = -1;
bfs();
for (i = 0; i < M; i++) {
if (arr[U[i]] == arr[V[i]]) ret[i] = arr[U[i]];
else {
ll u, v;
u = min(arr[U[i]], arr[V[i]]);
v = max(arr[U[i]], arr[V[i]]);
if (u == 0 && v == 1) ret[i] = 0;
if (u == 1 && v == 2) ret[i] = 1;
if (u == 0 && v == 2) ret[i] = 2;
}
}
return ret;
}
ret.resize(M);
deg.resize(N);
ll i;
for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
for (i = 0; i < M; i++) num[U[i]].push_back(i);
for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
for (i = 0; i < M; i++) num[V[i]].push_back(i);
for (i = 0; i < M; i++) deg[U[i]]++, deg[V[i]]++;
depth.resize(N);
dfs();
return ret;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
namespace {
int A, B;
int variable_example = 0;
ll pv;
ll str;
ll last;
string up[6], down[6];
bool chk(string s) {
for (ll i = 0; i < 6; i++) {
if (s == up[i]) return true;
}
return false;
}
string s;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
pv = -1;
str = 0;
last = 0;
up[0] = "00101";
up[1] = "01011";
up[2] = "10110";
up[3] = "01100";
up[4] = "11001";
up[5] = "10010";
}
int Move(std::vector<int> y) {
if (A != 2) {
if (y[0] && y[1]) return 0;
if (y[1] && y[2]) return 1;
if (y[2] && y[0]) return 2;
if (y[0]) return 0;
if (y[1]) return 1;
if (y[2]) return 2;
}
if (pv != -1) {
if ((y[0] + y[1] + 1) != 2) {
str = 0;
s.clear();
last = 1;
y[pv]++;
if (y[0] == 1) {
if (pv == 0) return -1;
else return pv = 0;
}
else {
if (pv == 1) return -1;
else return pv = 1;
}
}
else {
if (!last) {
str++;
ll nxt;
if (y[0]) nxt = 0;
else nxt = 1;
s.push_back(nxt + 48);
if (str == 5) {
if (chk(s)) {
last = 1;
str = 0;
s.clear();
return pv = nxt;
}
else {
last = 1;
str = 0;
s.clear();
return -1;
}
}
else {
return pv = nxt;
}
}
else {
if (!(y[0] + y[1])) return -1;
if (y[0]) return pv = 0;
else return pv = 1;
}
}
}
else {
if ((y[0] + y[1]) != 2) {
last = 1;
if (!(y[0] + y[1])) return -1;
if (y[0] == 1) return pv = 0;
else return pv = 1;
}
else {
if (y[0] == 2) {
s.push_back('0');
s.push_back('0');
str += 2;
return pv = 0;
}
else if (y[1] == 2) {
s.push_back('1');
s.push_back('1');
str += 2;
return pv = 1;
}
else {
s.push_back('0');
s.push_back('1');
str += 2;
return pv = 1;
}
}
}
}
