//include "Anthony.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>
const int maxn = 20000, k = 6;
int d[maxn];
vi graph[maxn];
queue<int> q;
int s[k] = {0, 0, 1, 0, 1, 1};
vi ans;
vi Mark(int n, int m, int a, int b, vi u, vi v){
ans.resize(m);
for(int i = 0; i < m; i++){
graph[u[i]].push_back(i);
graph[v[i]].push_back(i);
}
if(a > 2){
q.push(0);
while(!q.empty()){
int c = q.front();
q.pop();
for(int i : graph[c]){
int j = u[i] ^ v[i] ^ c;
if(j && !d[j]){
d[j] = d[c] + 1;
q.push(j);
}
if(d[j] == d[c] || d[j] == d[c] + 1){
ans[i] = d[c] % 3;
}
}
}
}else{
function<void(int, int)> dfs = [&](int c, int p){
for(int i : graph[c]){
int j = u[i] ^ v[i] ^ c;
if(j != p){
ans[i] = s[d[c] % k];
d[j] = graph[j].size() > 2 ? (ans[i] ^ 1) << 1 : d[c] + 1;
dfs(j, c);
}
}
};
dfs(0, -1);
}
return ans;
}
//#include "Catherine.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>
int a, b;
int prv = -1;
void Init(int A, int B){
a = A, b = B;
}
int Move(vi v){
if(a > 2){
if(~prv) v[prv]++;
for(int i = 0; i < 3; i++){
if(v[i] && v[(i + 1) % 3]) return prv = i;
}
for(int i = 0; i < 3; i++){
if(v[i]) return prv = i;
}
}
return -1;
}
