#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
vector<array<int, 2>> ad[20005];
vector<int> ans;
string pattern = "110100";
bool visited[20005];
void dfs(int u, int par_color, int pat)
{
visited[u] = 1;
if(par_color == -1){
for(auto &[v, idx] : ad[u]){
ans[idx] = 0;
dfs(v, 0, -1);
}
return;
}
int child = 0;
for(auto &[v, idx] : ad[u]) if(visited[v] == 0) child++;
if(child == 1){
int cur = (pat+1)%6;
if(pat == -1){
if(par_color == 1) cur = 1;
else cur = 3;
}
for(auto &[v, idx] : ad[u]) if(visited[v] == 0){
ans[idx] = pattern[cur] - '0';
dfs(v, pattern[cur] - '0', cur);
}
}
else{
for(auto &[v, idx] : ad[u]) if(visited[v] == 0){
ans[idx] = par_color^1;
dfs(v, par_color^1, -1);
}
}
visited[u] = 0;
}
vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
//Solve for the case A = 2, B = 6;
ans.resize(m);
for(int i = 0; i < m; i++){
ad[U[i]].push_back({V[i], i});
ad[V[i]].push_back({U[i], i});
}
dfs(0, -1, -1);
return ans;
}
#include "Catherine.h"
#include<bits/stdc++.h>
using namespace std;
int A, B;
string patte = "110100";
vector<string> correct_pattern;
void Init(int a, int b) {
A = a; B = b;
patte += patte;
for(int i = 0; i < 6; i++){
string cur = "";
for(int j = i; j < i+5; j++) cur += patte[j];
correct_pattern.push_back(cur);
}
}
/**/
int wrong = 0, moves_count = -1;
stack<int> last_color;
string cur_pattern = "";
bool first_turn = 0;
int Move(vector<int> f) {
moves_count++;
if(first_turn == 0){
first_turn = 1;
if(f[0] + f[1] == 1){
wrong = -1; //Always right
if(f[0] > 0){
last_color.push(0); return 0;
}
else{
last_color.push(1); return 1;
}
}
else if(f[0] + f[1] == 2){
if(f[0] == f[1]){
cur_pattern += "10";
last_color.push(0); return 0;
}
else if(f[1] == 0){
cur_pattern += "00";
last_color.push(0); return 0;
}
else{
cur_pattern += "11";
last_color.push(1); return 1;
}
}
else{
wrong = -1; //Always right
if(f[0] < f[1]){
last_color.push(0); return 0;
}
else{
last_color.push(1); return 1;
}
}
}
if(wrong == 0){
if(f[0] + f[1] == 0){
//Return if dead end
wrong = -1; return -1;
}
else if(f[0] + f[1] > 1){
int cur_last_color = last_color.top();
if(f[cur_last_color] == 0){wrong = -1; return -1;}
else{wrong = -1; last_color.push(cur_last_color^1); return last_color.top();}
}
else{
if(f[0] > 0) cur_pattern += "0";
else cur_pattern += "1";
if(cur_pattern.size() == 5){
bool ok = 1;
for(string i : correct_pattern) if(i == cur_pattern) ok = 0;
if(ok == 0){wrong = -1; return -1;}
else{
wrong = -1;
if(f[0] > 0) last_color.push(0);
else last_color.push(1);
return last_color.top();
}
}
else{
if(f[0] > 0) last_color.push(0);
else last_color.push(1);
return last_color.top();
}
}
}
else{
//cerr<<"A"<<f[0]<<" "<<f[1]<<endl;
if(f[0] + f[1] == 1){
if(f[0] > 0) last_color.push(0);
else last_color.push(1);
return last_color.top();
}
else{
last_color.push(last_color.top()^1);
return last_color.top();
}
}
}
