#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace {
int n, m, a, b;
vector<pair<int, int> > link[20002];
vector<int> ans;
int dist[20002];
int col[20002], road[20002];
void bfs(){
queue<pair<int, int> > que;
dist[0] = 1;
que.push(make_pair(0, 1));
while(!que.empty()){
pair<int, int> tmp = que.front(); que.pop();
int x = tmp.first, d = tmp.second;
dist[x] = d;
for(auto y: link[x]){
if(dist[y.first]) continue;
dist[y.first] = d+1;
que.push(make_pair(y.first, d+1));
}
}
}
const int pattern[] = {0, 0, 1, 0, 1, 1};
void dfs(int x, int par = -1, int cnt = 0){
if(x==0){
for(auto y: link[x]){
col[y.second] = pattern[cnt%6];
road[y.first] = y.second;
dfs(y.first, x, (cnt+1)%6);
}
return;
}
if((int)link[x].size() == 1) return;
if((int)link[x].size() == 2){
for(auto y: link[x]){
if(y.first == par) continue;
col[y.second] = pattern[cnt];
road[y.first] = y.second;
dfs(y.first, x, (cnt+1)%6);
}
return;
}
if(col[road[x]]) cnt = 1;
else cnt = 3;
for(auto y: link[x]){
if(par == y.first) continue;
col[y.second] = !col[road[x]];
road[y.first] = y.second;
dfs(y.first, x, cnt);
}
}
}
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;
for(int i=0; i<m; i++) link[U[i]].push_back(make_pair(V[i], i)), link[V[i]].push_back(make_pair(U[i], i));
if(A >= 3){
bfs();
for(int i=0; i<m; i++){
ans.push_back((min(dist[U[i]], dist[V[i]]) + 2) % 3);
}
return ans;
}
else{
ans.resize(m);
dfs(0);
return vector<int> (col, col+m);
}
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B;
int pattern[] = {1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0};
bool strange = 1;
int cnt = 0;
int prv = -1;
vector<int> vb;
}
void Init(int A, int B) {
::A = A;
::B = B;
prv = -1, cnt = 0, strange = 1;
}
int Move(vector<int> y){
if(A >= 3){
vector<int> lVec;
for(int i=0; i<A; i++) for(int j=0; j<y[i]; j++) lVec.push_back(i);
y = lVec;
int MIN = *min_element(y.begin(), y.end());
int MAX = *max_element(y.begin(), y.end());
if(MIN==MAX) return MIN;
return MAX==1 ? 0 : MIN==1 ? 1 : 2;
}
int c0 = y[0], c1 = y[1];
cnt++;
if(cnt > 6) strange = 0;
if(!strange){
if(!c0) return prv=1;
if(!c1) return prv=0;
if(prv == 0) c0++;
if(prv == 1) c1++;
if(c0 == 1) return prv=0;
if(c1 == 1) return prv=1;
}
if(prv == 0) c0++;
if(prv == 1) c1++;
if(prv == -1){
if(c0+c1==1){
strange = 0;
if(c0) return prv=0;
return prv=1;
}
if(c0+c1>2){
strange = 0;
if(c0==1) return prv=0;
if(c1==1) return prv=1;
}
if(c0==2){
vb.push_back(0);
vb.push_back(0);
return prv=0;
}
else if(c1==2){
vb.push_back(1);
vb.push_back(1);
return prv=1;
}
else{
vb.push_back(0);
vb.push_back(1);
return prv=1;
}
}
if(c0+c1>2){
strange = 0;
if(c0==1){
if(prv==0) return -1;
return prv = 0;
}
if(c1==1){
if(prv==1) return -1;
return prv=1;
}
}
if(c0+c1==1){
strange = 0;
return -1;
}
vb.push_back(y[0] ? 0 : 1);
bool possible = 0;
for(int i=0; i<6; i++){
bool diff=0;
for(int j=0; j<(int)vb.size(); j++){
if(pattern[i+j] != vb[j]) diff=1;
}
if(!diff) possible=1;
}
if(!possible){
strange=0;
return -1;
}
return prv = y[0]?0:1;
}
