#include "Anthony.h"
#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
using pii = pair<int, int>;
namespace {
vector<int> magic;
vector<vector<pii>> g;
vector<int> ans;
} // namespace
void dfs(int now, int p, int top, int len){
int cnt = 0;
for(pii i : g[now]){
if(i.F == p) continue;
cnt++;
}
int nxt = !top;
if(cnt == 1){
if(len == -1){
if(top == 0) len = 0;
else len = 1;
}
len++;
//cerr << "two " << now << " " << len << "\n";
nxt = magic[len % 6];
}
else len = -1;
for(pii i : g[now]){
if(i.F == p) continue;
ans[i.S] = nxt;
dfs(i.F, now, nxt, len);
}
}
vector<int> Mark(int n, int m, int A, int B,
vector<int> U, vector<int> V) {
magic = {0, 1, 0, 0, 1, 1};
ans.resize(m);
g.resize(n);
for(int i = 0; i < m; i++){
int u = U[i], v = V[i];
g[u].eb(mp(v, i));
g[v].eb(mp(u, i));
}
dfs(0, 0, 1, -1);
//printv(ans, cerr);
return ans;
}
#include "Catherine.h"
#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
namespace {
int A, B;
int lst = -1;
vector<int> magic;
deque<int> tmp;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
magic = {0, 1, 0, 0, 1, 1};
}
bool check(){
while(tmp.size() > 5) tmp.pop_front();
if(tmp.size() < 5) return false;
for(int i = 0; i < 6; i++){
bool ok = true;
for(int j = 0; j < 5; j++){
if(tmp[j] != magic[(i + j) % 6]) ok = false;
}
if(ok) return true;
}
return false;
}
int Move(vector<int> y) {
if(lst != -1) y[lst]++;
int deg = 0;
for(int i : y) deg += i;
if(deg >= 3){
int r;
for(int i = 0; i < 2; i++){
if(y[i] != 1) continue;
if(i == lst) r = -1;
else r = lst = i;
}
tmp.clear();
tmp.eb(lst);
//cerr << "test " << r << "\n";
return r;
}
//cerr << "check ";
//printv(tmp, cerr);
if(check()){
tmp.clear();
tmp.eb(lst);
return -1;
}
int nxt = -1;
if(lst != -1) y[lst]--;
for(int i = 0; i < 2; i++){
if(y[i]){
nxt = i;
//break;
}
}
lst = nxt;
tmp.eb(nxt);
//cerr << nxt << "\n";
return nxt;
}
