#include <bits/stdc++.h>
#include "Anthony.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
namespace {
vector<pair<int,int>> v[20002];
int n,m;
int deg[20002] = {0};
int cc[6] = {0,1,1,0,0,1};
vector<int> ret;
}
void dfs(int node, int b, int c, int lst){
if(deg[node]>=3){
for(pair<int,int> nxt:v[node])if(nxt.first!=b){
ret[nxt.second] = 1-lst;
if(lst==1)dfs(nxt.first,node,1,1-lst);
else dfs(nxt.first,node,0,1-lst);
}
return;
}
for(pair<int,int> nxt:v[node])if(nxt.first!=b){
ret[nxt.second] = cc[c];
dfs(nxt.first,node,(c+1)%6,cc[c]);
}
}
std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
n = N,m = M;
for(int i=0;i<m;i++){
v[U[i]].push_back({V[i],i});
v[V[i]].push_back({U[i],i});
deg[U[i]]++;
deg[V[i]]++;
}
for(int i=0;i<m;i++)ret.push_back(0);
for(pair<int,int> nxt:v[0]){
ret[nxt.second] = 0;
dfs(nxt.first,0,1,0);
}
return ret;
}
#include <bits/stdc++.h>
#include "Catherine.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
namespace {
bool tf=false;
int lst = -1;
vector<int> cv;
}
void Init(int A, int B) {
tf=false;
lst = -1;
cv.clear();
}
bool ff(vector<int> cv){
if(cv[0]==2 && cv[1]==1 && cv[2]==2 && cv[3]==0)return false;
if(cv[0]==1 && cv[1]==2 && cv[2]==0 && cv[3]==2)return false;
if(cv[0]==2 && cv[1]==0 && cv[2]==2 && cv[3]==2)return false;
if(cv[0]==0 && cv[1]==2 && cv[2]==2 && cv[3]==2)return false;
if(cv[0]==2 && cv[1]==2 && cv[2]==2 && cv[3]==1)return false;
if(cv[0]==2 && cv[1]==2 && cv[2]==1 && cv[3]==2)return false;
return true;
}
int Move(std::vector<int> y) {
if(tf){
//assert(lst!=-1);
if(y[0]==1 && y[1]==0){
lst = 0;
return 0;
}
else if(y[0]==0 && y[1]==1){
lst = 1;
return 1;
}
y[lst]++;
if(y[lst]==1)return -1;
if(y[0]==1){
lst = 0;
return 0;
}
else{
//assert(y[1]==1);
lst = 1;
return 1;
}
}
if(lst==-1){
if(y[0]+y[1]>=3){
if(y[0]==1){
lst = 0;
tf=true;
return 0;
}
else{
//assert(y[1]==1);
lst = 1;
tf=true;
return 1;
}
}
//assert(y[0]+y[1]!=0);
if(y[0]+y[1]==1){
if(y[0]==1){
lst = 0;
tf=true;
return 0;
}
else{
//assert(y[1]==1);
lst = 1;
tf=true;
return 1;
}
}
//assert(y[0]+y[1]==2);
int c = -1;
if(y[0]==2 && y[1]==0){
c = 0;
}
if(y[0]==0 && y[1]==2)c = 1;
else c = 2;
cv.push_back(c);
if(y[0]>=1){
lst = 0;
return 0;
}
else{
lst = 1;
return 1;
}
}
if(y[0]+y[1]>=2){
y[lst]++;
//assert(y[0]==1 || y[1]==1);
if(y[0]==1){
if(lst==0){
tf=true;
return -1;
}
tf=true;
lst = 0;
return 0;
}
else{
if(lst==1){
tf=true;
return -1;
}
tf=true;
lst = 1;
return 1;
}
}
if(y[0]+y[1]==0){
tf=true;
return -1;
}
y[lst]++;
int c = -1;
if(y[0]==2 && y[1]==0)c = 0;
else if(y[0]==0 && y[1]==2)c = 1;
else c = 2;
cv.push_back(c);
if((int)cv.size()==4){
tf=true;
if(!ff(cv)){
return -1;
}
}
y[lst]--;
if(y[0]>=1){
lst = 0;
return 0;
}
else{
lst = 1;
return 1;
}
}
