#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int n,m,a,b;
const int maxn=2e4;
string s;
vector<pair<int,int> >adj[maxn+2];
int dist[maxn+2];
int col[maxn+2];
} // namespace
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
n=N,m=M,a=A,b=B;
s="101001";
for(int q=0;q<U.size();q++){
adj[U[q]].push_back({V[q],q}); adj[V[q]].push_back({U[q],q});
}
for(int q=0;q<N;q++)dist[q]=1e9;
dist[0]=0; col[0]=0;
queue<pair<int,int> >qu; qu.push({0,-1});
while(qu.size()){
auto [cur,id]=qu.front(); qu.pop();
for(auto [x,nxt] : adj[cur]){
if(dist[x]>dist[cur]+1){
dist[x]=dist[cur]+1;
if(id==-1){
col[nxt]=0; qu.push({x,nxt});
continue;
}
if(adj[cur].size()>2){
if(s[col[id]]=='1'){
col[nxt]=1;
}
else{
col[nxt]=0;
}
}
else{
col[nxt]=(col[id]+1)%6;
}
qu.push({x,nxt});
}
}
}
vector<int>ans(M);
for(int q=0;q<M;q++){
ans[q]=s[col[q]]-'0';
//cout<<ans[q]<<endl;
}
if(A!=2){
for(int q=0;q<M;q++){
if(dist[U[q]]>dist[V[q]])swap(U[q],V[q]);
ans[q]=dist[U[q]]%3;
}
}
return ans;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B;
int lst=-1;
string tmp="",s="101001101001";
bool oke=false;
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(vector<int> freq) {
if(A!=2){
if(lst!=-1){
lst--; lst=(lst+3)%3;
}
else{
if(freq[0] && freq[1])return lst=0;
if(freq[0] && freq[2])return lst=2;
if(freq[2] && freq[1])return lst=1;
for(int q=0;q<3;q++){
if(freq[q])return lst=q;
}
}
return lst;
}
int freq2[2];
for(int q=0;q<2;q++)freq2[q]=freq[q];
int deg=0;
if(lst!=-1)freq2[lst]++;
for(int q=0;q<2;q++)deg+=freq2[q];
int ans=lst;
if(deg==2){
if(oke){
for(int q=0;q<2;q++){
if(freq[q]==1)ans=q;
}
}
else{
for(int q=0;q<2;q++){
for(int w=0;w<freq[q];w++){
tmp+=('0'+q);
}
}
if(tmp.length()==5){
oke=true;
bool ul=false;
for(int q=0;q<6;q++){
if(s.substr(q,5)==tmp){
ul=true;
}
}
if(ul){
ans=-1;
}
else{
for(int q=0;q<2;q++){
if(freq[q]==1)ans=q;
}
}
}
else{
ans=tmp.back()-'0';
}
}
}
else{
oke=true;
for(int q=0;q<2;q++){
if(freq2[q]==1)ans=q;
}
if(ans==lst)ans=-1;
}
if(lst==-1 && ans==-1){
if(deg==2)assert(1==2);
}
if(ans!=-1)lst=ans;
return ans;
}
