#include "Anthony.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)x.size()
const int N = 2e4+5;
namespace sol1{
vector<int> res;
vector<int> patt = {0, 1, 1, 0, 0, 1};
vector<pair<int, int>> edges[N];
void dfs(int u, int p = -1, int cur = 0, int in = 0){
for(auto x : edges[u]){
if(x.ff == p) continue;
if(sz(edges[u]) == 2){
res[x.ss] = patt[in];
dfs(x.ff, u, res[x.ss], (in + 1) % 6);
} else {
res[x.ss] = cur ^ 1;
if(cur) dfs(x.ff, u, cur ^ 1, 1);
else dfs(x.ff, u, cur ^ 1, 2);
}
}
}
vector<int> Mark1(int n, int m, int a, int b, vector<int> u, vector<int> v){
res.resize(m);
for(int i=0;i<m;i++){
int a = u[i] + 1, b = v[i] + 1;
edges[a].pb({b, i}), edges[b].pb({a, i});
res[i] = -1;
}
edges[1].pb({-1, -1});
dfs(1);
//~ for(int i=0;i<m;i++) cout<<res[i]<<" ";
//~ cout<<"\n";
return res;
}
}
namespace sol2{
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
const int N = 2e4+5;
vector<int> edges[N], res, dd;
//~ const int inf = ;
vector<int> Mark2(int n, int m, int a, int b, vector<int> u, vector<int> v){
res.resize(m);
for(int i=0;i<m;i++){
int a = u[i] + 1, b = v[i] + 1; cin>>a>>b;
edges[a].pb(b), edges[b].pb(a);
} queue<int> qq;
qq.push(1);
dd.assign(n+1, 1e9+7); dd[1] = 0;
while(!qq.empty()){
int u = qq.front(); qq.pop();
for(auto x : edges[u]){
if(umin(dd[x], dd[u] + 1)) qq.push(x);
}
}
for(int i=0;i<m;i++){
int a = u[i] + 1, b = v[i] + 1;
res[i] = min(dd[a], dd[b]) % 3;
} return res;
}
}
vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v) {
if(a == 2) {
return sol1::Mark1(n, m, a, b, u, v);
} else {
return sol2::Mark2(n, m, a, b, u, v);
}
}
#include "Catherine.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
vector<int> path;
int a;
void Init(int a, int b) { ::a = a; }
namespace sol1{
vector<int> ppat = {0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1};
int ok = 0, last = -1;
vector<int> path;
int Move(vector<int> y){
if(ok){
assert(~last);
if(y[0] + y[1] + 1 > 2) return last ^= 1;
if(y[0] == 0) return last = 1;
if(y[1] == 0) return last = 0;
assert(0);
}
if(y[0] + y[1] + (last != -1) > 2){
ok = 1;
if(~last){
if(min(y[0], y[1]) == 0) return -1;
if(min(y[0], y[1]) == 1) return last ^= 1;
assert(0);
} else {
if(y[0] == 1) return last = 0;
if(y[1] == 1) return last = 1;
assert(0);
}
}
if(y[0] + y[1] + (last != -1) == 1){
ok = 1;
if(y[0] == 1) return last = 0;
if(y[1] == 1) return last = 1;
return -1;
}
if(last == -1){
if(y[0] == 2) { path.pb(0), path.pb(0); return last = 0; }
else if(y[1] == 2) { path.pb(1), path.pb(1); return last = 1; }
else { path.pb(0), path.pb(1); return last = 1; }
}
else {
if(y[0] == 1) last = 0, path.pb(0);
if(y[1] == 1) last = 1, path.pb(1);
if(sz(path) == 5){ ok = 1;
for(int i=0;i+5<=sz(ppat);i++){
int l = i, r = i + 5 - 1, okk = 1;
for(int j=l;j<=r;j++) okk &= (ppat[j] == path[j-i]);
if(okk) return -1;
} if(y[0]) return last = 0;
else return last = 1;
} else return last;
}
}
}
namespace sol2{
int Move(vector<int> y){
int c0 = y[0], c1 = y[1], c2 = y[2];
if(c0 > 0 && c1 >= 0 && c2 == 0) return 0;
if(c1 > 0 && c2 >= 0 && c0 == 0) return 1;
if(c2 > 0 && c0 >= 0 && c1 == 0) return 2;
}
}
int Move(vector<int> y) {
if(a == 2) return sol1::Move(y);
else return sol2::Move(y);
}
