#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef sus
#define cerr if (0) cerr
#endif
const int N=2e4+10;
namespace sub1234{
vector<int> g[N];
vector<int> ans;
int dep[N];
void bfs(){
memset(dep, -1, sizeof dep);
queue<int> q;
q.push(0); dep[0]=0;
while (q.size()){
int u=q.front(); q.pop();
for (int v:g[u]){
if (dep[v]==-1){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
}
vector<int> solve(int n, int m, vector<int> u, vector<int> v){
ans.resize(m, -1);
for (int i=0; i<m; ++i){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
bfs();
for (int i=0; i<m; ++i){
ans[i]=min(dep[u[i]], dep[v[i]])%3;
cerr << u[i] << ' ' << v[i] << ' ' << ans[i] << '\n';
}
return ans;
}
}
namespace sub567{
string sussy="011001";
vector<int> path;
vector<pair<int, int>> g[N];
vector<int> ans;
int par_idx[N];
void dfs(int u, int p){
pair<int, int> pp={-1, -1};
for (auto &e:g[u]) if (e.first==p) pp=e;
if (pp.first!=-1) g[u].erase(find(g[u].begin(), g[u].end(), pp));
if ((int)g[u].size()==1){
if (path.empty()) path.push_back(par_idx[u]);
path.push_back(g[u][0].second);
par_idx[g[u][0].first]=g[u][0].second;
dfs(g[u][0].first, u);
}else{
if (path.size()){
int first_edge=path[0]==-1?0:ans[path[0]]^1;
path.erase(path.begin());
for (int i=0; i<(int)path.size(); ++i) ans[path[i]]=sussy[(i+first_edge)%6]-'0';
}
path.clear();
for (auto &e:g[u]){
int v=e.first, i=e.second;
ans[i]=par_idx[u]==-1?0:ans[par_idx[u]]^1;
par_idx[v]=i;
if ((int)g[v].size()==1){
path.clear();
path.push_back(par_idx[u]);
}
dfs(v, u);
}
}
}
vector<int> solve(int n, int m, vector<int> u, vector<int> v){
ans.resize(m);
par_idx[0]=-1;
for (int i=0; i<m; ++i){
g[u[i]].emplace_back(v[i], i);
g[v[i]].emplace_back(u[i], i);
}
dfs(0, -1);
for (int i=0; i<m; ++i) cerr << u[i] << ' ' << v[i] << ' ' << ans[i] << '\n';
return ans;
}
}
vector<int> Mark(int n, int m, int a, int b,
vector<int> u, vector<int> v) {
if (a!=2){
return sub1234::solve(n, m, u, v);
}
return sub567::solve(n, m, u, v);
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef sus
#define cerr if (0) cerr
#endif
int a, b;
void Init(int A, int B) {
a=A;
b=B;
}
vector<pair<int, int>> v;
string sussy="011001";
bool check_sus(){
if ((int)v.size()<5) return 0;
string lmao;
for (int i=5; i>=1; --i){
if (v.end()[-i].first!=1) return 0;
lmao.push_back('0'+v.end()[-i].second);
}
cerr << "check " << lmao << endl;
if ((sussy+sussy).find(lmao)!=string::npos){
cerr << "sus " << lmao << endl;
return 1;
}
return 0;
}
int Move(vector<int> y) {
if (a!=2){
if (y[0] && y[1]) return 0;
if (y[1] && y[2]) return 1;
if (y[2] && y[0]) return 2;
for (int i=0; i<3; ++i) if (y[i]) return i;
}
if (y[0]+y[1]==1){
if (y[0]){
v.emplace_back(1, 0);
if (check_sus()){
v.emplace_back(-1, v.back().second);
return -1;
}
return 0;
}else{
v.emplace_back(1, 1);
if (check_sus()){
v.emplace_back(-1, v.back().second);
return -1;
}
return 1;
}
}
if (v.size()){
int lst=v.back().second;
if (y[lst^1]==1){
v.emplace_back(0, lst^1);
return lst^1;
}
v.emplace_back(-1, lst);
return -1;
}
if (y[0]==1 && y[1]==1){
v.emplace_back(1, 0);
v.emplace_back(1, 1);
return 1;
}
if (y[0]==2){
v.emplace_back(1, 0);
v.emplace_back(1, 0);
return 0;
}
if (y[1]==2){
v.emplace_back(1, 1);
v.emplace_back(1, 1);
return 1;
}
if (y[1]==1){
v.emplace_back(y[0]<=1, 1);
return 1;
}
if (y[0]==1){
v.emplace_back(y[1]<=1, 0);
return 0;
}
if (y[1]){
v.emplace_back(0, 1);
return 1;
}
if (y[0]){
v.emplace_back(0, 0);
return 0;
}
return -1;
}
