#include <bits/stdc++.h>
using namespace std;
namespace {
vector<int> strat1(int N, int M, int A, int B,
vector<int> U, std::vector<int> V) {
// General Graph A=3
vector<int> ans(M,-1);
vector<vector<pair<int,int>>> adj(N);
for(int i=0;i<M;i++){
adj[U[i]].emplace_back(V[i],i);
adj[V[i]].emplace_back(U[i],i);
}
vector<bool> visited(N);
queue<pair<int,int>> q;
q.emplace(0,0);
while(!q.empty()){
auto [idx,col] = q.front();q.pop();
if(visited[idx])continue;
visited[idx]=true;
for(auto&i:adj[idx]){
if(ans[i.second]==-1)ans[i.second]=col;
if(!visited[i.first])q.emplace(i.first,(col+1)%3);
}
}
return ans;
}
vector<bool> magic = {1,1,0,0,1,0};
vector<vector<pair<int,int>>> adj;
vector<bool> ans;
void dfs(int x,int p,bool parcol,int seqidx){
if(adj[x].size()==1)return;
if(adj[x].size()==2){
// Colour using sequence
seqidx = (seqidx+1)%6;
if(adj[x][0].first==p)swap(adj[x][0],adj[x][1]);
if(magic[seqidx]){
ans[adj[x][0].second]=true;
dfs(adj[x][0].first,x,true,seqidx);
} else {
dfs(adj[x][0].first,x,false,seqidx);
}
return;
}
// Colour using b&w
for(auto&i:adj[x])if(i.first!=p){
if(parcol){
dfs(i.first,x,false,2);
} else {
ans[i.second]=true;
dfs(i.first,x,true,0);
}
}
}
vector<int> strat2(int N, int M, int A, int B,
vector<int> U, std::vector<int> V) {
// Tree A=2,B=6
adj = vector<vector<pair<int,int>>>(N);
ans = vector<bool>(M);
for(int i=0;i<M;i++){
adj[U[i]].emplace_back(V[i],i);
adj[V[i]].emplace_back(U[i],i);
}
for(auto&i:adj[0]){
dfs(i.first,0,false,2);
}
vector<int> col(M);
for(int i=0;i<M;i++)if(ans[i])col[i]=1;
return col;
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B,
vector<int> U, std::vector<int> V) {
if(A>=3)return strat1(N,M,A,B,U,V);
else return strat2(N,M,A,B,U,V);
}
#include <bits/stdc++.h>
using namespace std;
namespace {
int A, B;
int strat1(vector<int> y) {
// General Graph A=3
bool more0 = y[0]>0;
bool more1 = y[1]>0;
bool more2 = y[2]>0;
if(more0 and more1)return 0;
if(more1 and more2)return 1;
if(more2 and more0)return 2;
if(more0)return 0;
if(more1)return 1;
if(more2)return 2;
assert(false);
}
vector<bool> magic = {1,1,0,0,1,0};
vector<vector<int>> good = {
{0,1,1,0,0},
{1,0,1,1,0},
{0,1,0,1,1},
{0,0,1,0,1},
{1,0,0,1,0},
{1,1,0,0,1},
};
// False phase is detection phase
// True phase is travelling phase
bool phase = false;
int lastmov = -1;
vector<int> currseq;
int strat2(vector<int> y) {
// Tree A=2,B=6
if(phase){
if(y[0]==1 and y[1]==1)y[lastmov]++;
if(y[0]==1){
lastmov = 0;
return 0;
}
lastmov = 1;
return 1;
}
if((y[0]==0 and y[1]==0) or (lastmov==-1 and y[0]+y[1]<2)){
// We are at a leaf
phase = true;
if(lastmov==-1){
if(y[0]==1){
lastmov = 0;
return 0;
}
assert(y[1]);
lastmov = 1;
return 1;
}
return -1;
}
// Emplace current situation into sequence
if(lastmov==-1){
if(y[0]+y[1]>2){ // Non-line node
phase = true;
if(y[0]==1){
lastmov = 0;
return 0;
}
lastmov = 1;
return 1;
}
if(y[0]==2){
currseq = {0,0};
lastmov = 0;
return 0;
} else if(y[1]==2){
currseq = {1,1};
lastmov = 1;
return 1;
} else {
currseq = {0,1};
lastmov = 1;
return 1;
}
} else {
if(y[0]+y[1]>=2){ // Non-line node
y[lastmov]++;
phase = true;
if(y[0]==1){
if(lastmov==0)return -1;
lastmov = 0;
return 0;
}
if(lastmov==1)return -1;
lastmov = 1;
return 1;
}
if(y[0]==1){
currseq.emplace_back(0);
if(currseq.size()!=5){
lastmov = 0;
return 0;
}
} else {
currseq.emplace_back(1);
if(currseq.size()!=5){
lastmov = 1;
return 1;
}
}
}
if(currseq.size()==5){
phase = true;
if(find(good.begin(),good.end(),currseq)==good.end())return strat2(y);
else return -1;
}
assert(false);
}
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(vector<int> y) {
if(A>=3)return strat1(y);
else return strat2(y);
}
