#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
namespace {
bool st;
int n,m;
vector<int> al[20005];
int w[20005];
queue<int> q;
int d[20005];
int pat[20005];
int col[20005];
void dfs(int i,int p){
int child=0;
for (auto it:al[i]){
if (it==p) continue;
child++;
}
for (auto it:al[i]){
if (it==p) continue;
if (child>1){
pat[it]=col[it]=col[i]^1;
}
else{
pat[it]=(pat[i]+1)%7;
vector<int> C={0,1,0,0,1,1,1};
col[it]=C[pat[it]];
}
d[it]=d[i]+1;
dfs(it,i);
}
}
}
vector<signed> Mark(signed N, signed M, signed A, signed B,
vector<signed> U, vector<signed> V) {
st=(A>=3);
n=N,m=M;
rep(x,0,m){
al[U[x]].pub(V[x]);
al[V[x]].pub(U[x]);
}
if (st){
memset(w,-1,sizeof(w));
q.push(0);
w[0]=0;
while (!q.empty()){
int u=q.front(); q.pop();
for (auto it:al[u]) if (w[it]==-1){
w[it]=w[u]+1;
q.push(it);
}
}
vector<signed> res;
rep(x,0,m){
res.pub(min(w[U[x]],w[V[x]])%3);
//cout<<res.back()<<" "<<U[x]<<" "<<V[x]<<endl;
}
return res;
}
else{
dfs(0,-1);
vector<signed> res;
rep(x,0,m){
if (d[U[x]]>d[V[x]]) swap(U[x],V[x]);
res.pub(col[V[x]]);
}
//for (auto it:res) cout<<it<<" "; cout<<endl;
return res;
}
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
namespace {
bool st;
int PREV=-1;
set<string> good={
"01001",
"10011",
"00111",
"01110",
"11101",
"11010",
"10100"
};
bool dir=false;
string s="";
}
void Init(signed A, signed B) {
st=(A>=3);
}
signed Move(vector<signed> y) {
if (st){
vector<int> v;
rep(x,0,3) if (y[x] || PREV==x) v.pub(x);
sort(all(v));
if (sz(v)==1){
return PREV=v[0];
}
else if (v[1]==1){
return PREV=0;
}
else if (v[0]==1){
return PREV=1;
}
else{
return PREV=2;
}
}
else{
int tot=(PREV!=-1);
rep(x,0,2) tot+=y[x];
if (tot>=3){
dir=true;
if (PREV!=-1) y[PREV]++;
rep(x,0,2) if (y[x]==1){
if (PREV!=x) return PREV=x;
else return -1;
}
}
else if (tot==1){
dir=true;
if (PREV!=-1) y[PREV]++;
rep(x,0,2) if (y[x]==1){
if (PREV!=x) return PREV=x;
else return -1;
}
}
else if (dir){
rep(x,0,2) if (y[x]==1) return PREV=x;
}
else{
if (s==""){
rep(x,2,0) rep(z,0,y[x]) s+='0'+x;
//cout<<s<<endl;
rep(x,0,2) if (y[x]) return PREV=x;
}
else{
rep(x,0,2) rep(z,0,y[x]) s+='0'+x;
//cout<<s<<endl;
if (sz(s)==5){
dir=true;
if (!good.count(s)){
rep(x,0,2) if (y[x]==1) return PREV=x;
}
else{
return -1; //PREV is same
}
}
else{
rep(x,0,2) if (y[x]) return PREV=x;
}
}
}
}
}
