#include "Anthony.h"
#include <vector>
#include<bits/stdc++.h>
namespace {
using namespace std;
#define f first
#define s second
int A,B;
const int mxn=2e4+5;
vector<pair<int,int>> adj[mxn];
vector<int> ans;
vector<int> ch={0,0,1,0,1,1};
void dfs(int v,int p=-1,int c=0,int cur=-1){
for(auto u:adj[v]){
if(u.f==p) continue;
if(v!=0 and (int)adj[v].size()==2){
if(cur==-1){
if(c==0) cur=2;
else cur=0;
}
ans[u.s]=ch[cur];
dfs(u.f,v,ans[u.s],(cur+1)%6);
}
else{
ans[u.s]=(c+1)%2;
dfs(u.f,v,ans[u.s],-1);
}
}
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,std::vector<int> U, std::vector<int> V) {
::A = A;
::B = B;
ans.resize(M);
for(int i=0;i<M;i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
dfs(0);
//ans=vector<int>(M,0);
return ans;
}
#include "Catherine.h"
#include <vector>
#include<bits/stdc++.h>
namespace {
using namespace std;
#define all(x) x.begin(),x.end()
int A, B;
int variable_example = 0;
int prv=-1;
map<vector<int>,int> down,up;
vector<int> ch={0,0,1,0,1,1};
bool on=false;
bool dir=false;
vector<int> cur;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
for(int i=0;i<6;i++){
vector<int> tmp;
for(int j=0;j<5;j++){
tmp.push_back(ch[(i+j)%6]);
}
down[tmp]++;
}
reverse(all(ch));
for(int i=0;i<6;i++){
vector<int> tmp;
for(int j=0;j<5;j++){
tmp.push_back(ch[(i+j)%6]);
}
up[tmp]++;
}
}
int Move(std::vector<int> y) {
if(prv!=-1) y[prv]++;
if((y[0]>1 and y[1]==1) or (y[1]>1 and y[0]==1)){
dir=true;
if(y[0]>1){
if(prv==1){
prv=1;
return -1;
}
else{
prv=1;
return 1;
}
}
else{
if(prv==0){
prv=0;
return -1;
}
else{
prv=0;
return 0;
}
}
}
if(y[0]+y[1]==1){
dir=true;
if(y[0]==1){
if(prv==-1){
prv=0;
return 0;
}
else{
prv=0;
return -1;
}
}
else{
if(prv==-1){
prv=1;
return 1;
}
else{
prv=1;
return -1;
}
}
}
if(dir==true){
y[prv]--;
if(y[0]>0){
prv=0;
}
else{
prv=1;
}
return prv;
}
if(on==true){
cur.push_back(prv);
if((int)cur.size()==4){
y[prv]--;
if(y[0]>0) cur.push_back(0);
else cur.push_back(1);
y[prv]++;
if(up.find(cur)!=up.end()){
dir=true;
prv=cur.back();
return prv;
}
else{
dir=true;
return -1;
}
}
else{
y[prv]--;
if(y[0]>0){
prv=0;
return prv;
}
else{
prv=1;
return prv;
}
}
}
else{
on=true;
vector<int> edge;
for(int i=0;i<2;i++){
for(int j=0;j<y[i];j++) edge.push_back(i);
}
cur.push_back(edge[0]);
prv=edge[1];
return prv;
}
}
