#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) (int)(a).size()
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 2e4, f[] = {0, 1, 0, 0, 1, 1};
vector <pii> adj[NM+5];
vector <int> ans;
queue <int> q;
int dep[NM+5];
void bfs(){
for (int i = 0; i < NM; i++) dep[i] = -1;
dep[0] = 0;
while (!q.empty()) q.pop();
q.push(0);
while (!q.empty()){
int u = q.front(); q.pop();
for (pii _ : adj[u]){
int v = _.fi, id = _.se;
if (dep[v] != -1){
ans[id] = dep[v]%3;
}
else{
ans[id] = dep[u]%3;
dep[v] = dep[u]+1;
q.push(v);
}
}
}
}
void dfs(int u, int p, int m){
int child = isz(adj[u])-(p != -1);
if (child == 1 || p == -1){
for (pii _ : adj[u]){
int v = _.fi, id = _.se;
if (v == p) continue;
ans[id] = f[m];
dfs(v, u, (m+1)%6);
}
}
else{
for (pii _ : adj[u]){
int v = _.fi, id = _.se;
if (v == p) continue;
if (f[(m+5)%6] == 0){
ans[id] = 1;
dfs(v, u, 1);
}
else{
ans[id] = 0;
dfs(v, u, 0);
}
}
}
}
vector <int> Mark(int N, int M, int A, int B, vector <int> U, vector <int> V){
ans.resize(M);
for (int i = 0; i < M; i++){
adj[U[i]].push_back(mp(V[i], i));
adj[V[i]].push_back(mp(U[i], i));
}
if (A > 2){
bfs();
}
else{
dfs(0, -1, 0);
}
return ans;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
int A, B;
int nMove = 0;
bool oriented = 0;
int lst = -1;
string s = "";
int tmp = -1;
void Init(int _A, int _B){
A = _A, B = _B;
}
int Move(vector<int> y){
if (A > 2){
if (y[1] == 0 && y[2] == 0) return 0;
if (y[0] == 0 && y[2] == 0) return 1;
if (y[0] == 0 && y[1] == 0) return 2;
if (y[2] == 0) return 0;
if (y[0] == 0) return 1;
return 2;
}
++nMove;
if (oriented){
if (y[0] == 0) return lst = 1, 1;
if (y[1] == 0) return lst = 0, 0;
if (lst == 0) return lst = 1, 1;
return lst = 0, 0;
}
if (nMove == 1){
if (y[0] == 0 && y[1] == 1){
oriented = 1;
return lst = 1, 1;
}
if (y[1] == 0 && y[0] == 1){
oriented = 1;
return lst = 0, 0;
}
if (y[1] == 1 && y[0] > 1){
oriented = 1;
return lst = 1, 1;
}
if (y[0] == 1 && y[1] > 1){
oriented = 1;
return lst = 0, 0;
}
if (y[0] == 0 && y[1] == 2){
s.push_back('1');
tmp = 1;
return lst = 1, 1;
}
if (y[0] == 2 && y[1] == 0){
s.push_back('0');
tmp = 0;
return lst = 0, 0;
}
s.push_back('0');
tmp = 1;
return lst = 0, 0;
}
if (y[0] == 0 && y[1] == 0){
oriented = 1;
return -1;
}
if (y[0] == 0 && y[1] > 1){
oriented = 1;
return -1;
}
if (y[1] == 0 && y[0] > 1){
oriented = 1;
return -1;
}
if (y[0] > 0 && y[1] > 0){
oriented = 1;
if (lst == 0) return lst = 1, 1;
return lst = 0, 0;
}
if (nMove < 4){
if (y[0] > 0){
s.push_back('0');
return lst = 0, 0;
}
s.push_back('1');
return lst = 1, 1;
}
oriented = 1;
if (s == "001" && y[1] > 0) return -1;
if (s == "010" && y[0] > 0) return -1;
if (s == "101" && y[0] > 0) return -1;
if (s == "110" && y[1] > 0) return -1;
if (s == "100" && y[1] > 0 && tmp == 0) return -1;
if (s == "011" && y[0] > 0 && tmp == 0) return -1;
if (y[0] > 0) return lst = 0, 0;
return lst = 1, 1;
}
