#include "Anthony.h"
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const int inf = 1e9;
static vector<pii> g[20010];
static vector<int> ret;
static int tb[6] = {0, 1, 0, 0, 1, 1};
static void dfs(int x, int p, int k) {
int t = 1 - tb[k];
if(x != 0 && g[x].size() == 2) t = (k + 1) % 6;
for(auto i : g[x]) {
if(i.fi == p) continue;
ret[i.se] = tb[t];
dfs(i.fi, x, t);
}
}
std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
for(int i=0; i<M; i++)
g[U[i]].eb(V[i], i), g[V[i]].eb(U[i], i);
ret.resize(M, 0);
dfs(0, 0, 0);
/*for(auto i : ret) {
cout << i;
}
cout << endl;*/
return ret;
}
#include "Catherine.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;
static int typ;
void Init(int A, int B){
if(A>=3)typ=1;
else typ=2;
}
static int move_typeA(vector<int> vc){
for(int i=0; i<3; i++)if(vc[i]&&!vc[(i+2)%3])return i;
}
static int rpt[6]={0, 1, 0, 0, 1, 1};
static bool fnd;
static int cnt, prv=-1, mask;
static int move_typeB(vector<int> vc){
cnt++;
int deg=vc[0]+vc[1];
if(prv>=0)deg++;
if(fnd){
if(deg>=3){
prv=1-prv;
return prv;
}
if(vc[0])prv=0;
else prv=1;
return prv;
}
if(deg==1){
fnd=true;
if(cnt>1)return -1;
if(vc[0])prv=0;
else prv=1;
return prv;
}
if(deg>=3){
if(cnt>1)vc[prv]++;
fnd=true;
int tmp;
if(vc[0]==1)tmp=0;
else tmp=1;
if(tmp==prv&&cnt>1)return -1;
prv=tmp;
return tmp;
}
if(cnt<=3){
if(vc[0])prv=0;
else prv=1;
if(cnt==1)mask*=2, mask+=vc[1]-prv;
mask*=2, mask+=prv;
return prv;
}
if(cnt==4){
fnd=true;
int opp;
if(vc[0])opp=0;
else opp=1;
mask*=2, mask+=opp;
if(mask==25||mask==18||mask==5||mask==11||mask==22||mask==12){
prv=opp;
return prv;
}
return -1;
}
}
int Move(vector<int> y){
if(typ==1)return move_typeA(y);
return move_typeB(y);
}
