#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20'000 + 10;
int h[maxn], c[maxn];
vector<int> g[maxn];
int Q[maxn], tail, head;
int seq[] = {1, 1, 0, 0, 1, 0};
int col[maxn];
void dfs(int v, int idx = 0, int par = -1){
for (int i = 0; i < g[v].size(); i++){
if (g[v][i] == par){
g[v].erase(g[v].begin()+i);
break;
}
}
if (g[v].empty())
return;
if (g[v].size() == 1){
col[g[v][0]] = seq[idx];
dfs(g[v][0], (idx+1)%6, v);
return;
}
for (auto u : g[v]){
col[u] = 1-col[v];
dfs(u, 0, v);
}
}
void bfs(int v){
memset(h, -1, sizeof h);
Q[head++] = v;
h[v] = 0;
while (tail < head){
v = Q[tail++];
for (auto u : g[v])
if (h[u] == -1)
h[u] = h[v]+1, Q[head++] = u;
}
}
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
vector<int> X(m);
for (int i = 0; i < m; i++){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
bfs(0);
if (A >= 3){
for (int i = 0; i < m; i++){
int v = V[i], u = U[i];
if (h[v] == h[u])
X[i] = h[v]%3;
else
X[i] = (max(h[v],h[u])+2)%3;
}
return X;
}
dfs(0);
for (int i = 0; i < m; i++){
int v = V[i], u = U[i];
if (h[v] > h[u])
X[i] = col[v];
else
X[i] = col[u];
}
return X;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
int A, B, last = -1, sure = 0;
string s[] = {"111100", "021001", "110010", "200101", "111011", "110110"};
string now;
bool first;
void Init(int a, int b) {
A = a, B = b;
last = -1, sure = 0;
now.clear();
first = true;
}
int Move(vector<int> y){
if (A >= 3){
int a = -1, b = -1;
for (int j = 0; j < A; ++j) {
if (y[j] != 0){
if (a == -1)
a = j;
else
b = j;
}
}
if (b == -1)
return a;
if (a+1 == b)
return a;
return b;
}
int deg = y[0] + y[1] + (last != -1);
if (deg == 1){ // we are in a leaf
sure = true;
if (last != -1)
return -1;
assert(y[y[1]==1] > 0);
return last = (y[1] == 1);
}
if (deg > 2){
sure = true;
int nex = ((y[1] + (last==1)) == 1);
if (last == nex)
return -1;
assert(y[nex] > 0);
return last = nex;
}
if (sure){
assert(y[y[1]==1] > 0);
return last = (y[1] == 1);
}
if (first){
now += (char)(y[0]+'0');
now += (char)(y[1]+'0');
now += (char)((y[1]>0)+'0');
first = false;
assert(y[y[1]>0] > 0);
return last = (y[1] > 0);
}
now += (char)((y[1]==1)+'0');
if (now.size() == 6){
bool found = 0;
for (int j = 0; j < 6; j++)
if (now == s[j])
found = 1;
if (now.substr(2, 4) == "1100")
found = 1;
sure = 1;
if (found)
return -1;
assert(y[y[1]==1] > 0);
return last = (y[1] == 1);
}
assert(y[y[1]==1] > 0);
return last = (y[1] == 1);
}
