#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
namespace {
using namespace std;
vector<vector<pair<int,int> > > edges;
vector<int> marks;
vector<int> arr = {0, 1, 0, 0, 1, 1};
void dfs(int v, int pid, int idx){
if(pid >= 0) marks[pid] = arr[idx];
for(pair<int,int> e : edges[v]){
if(e.second == pid) continue;
if(edges[v].size() == 2){
dfs(e.first, e.second, (idx + 1) % 6);
} else {
dfs(e.first, e.second, 1 ^ arr[idx]);
}
}
}
void mark_tree(int n, int m, vector<int> u, vector<int> v){
edges.assign(n, {});
for(int i = 0; i < m; i++){
edges[u[i]].push_back({v[i], i});
edges[v[i]].push_back({u[i], i});
}
marks.resize(m);
dfs(0, -1, 0);
}
void mark_bfs(int n, int m, vector<int> u, vector<int> v){
vector<vector<int> > e(n);
for(int i = 0; i < m; i++){
e[u[i]].push_back(v[i]);
e[v[i]].push_back(u[i]);
}
vector<int> dist(n, -1);
vector<int> bfs;
int s = 0;
bfs.push_back(0);
dist[0] = 0;
while(s < (int)bfs.size()){
int x = bfs[s];
s++;
for(int w : e[x]){
if(dist[w] >= 0) continue;
dist[w] = dist[x] + 1;
bfs.push_back(w);
}
}
marks.resize(m);
for(int i = 0; i < m; i++){
marks[i] = min(dist[u[i]], dist[v[i]]) % 3;
}
}
vector<int> mark(int n, int m, int a, int b, vector<int> u, vector<int> v){
if(b > 0){
mark_tree(n, m, u, v);
} else {
mark_bfs(n, m, u, v);
}
return marks;
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
return mark(N, M, A, B, U, V);
}
#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
namespace {
using namespace std;
int a;
int b;
int last;
vector<int> seen;
bool good_to_go;
void init(int _a, int _b){
a = _a;
b = _b;
last = -1;
good_to_go = false;
}
int move_tree(vector<int> y){
vector<int> newy = y;
if(last >= 0) newy[last]++;
int deg = 0;
for(int x : newy) deg += x;
if(deg != 2){
good_to_go = true;
}
if(good_to_go){
if(deg == 1){
if(last == -1){
int r = 0;
while(y[r] != 1) r++;
last = r;
return r;
}
return -1;
} else if(deg == 2){
assert(last != -1);
int r = 0;
while(y[r] != 1) r++;
last = r;
return r;
} else {
int r = 0;
while(newy[r] != 1) r++;
if(y[r] != 1){
return -1;
} else {
last = r;
return r;
}
}
} else {
assert(seen.size() < 5);
if(last == -1){
int r = 0;
while(y[r] == 0) r++;
seen.push_back(r);
y[r]--;
r = 0;
while(y[r] == 0) r++;
last = r;
seen.push_back(r);
return r;
} else {
int r = 0;
while(y[r] == 0) r++;
seen.push_back(r);
if(seen.size() < 5){
last = r;
return r;
} else {
good_to_go = true;
vector<vector<int> > okay = {
{1, 1, 0, 0, 1},
{1, 0, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 1, 0, 1, 1},
{1, 0, 1, 1, 0},
{0, 1, 1, 0, 0},
};
for(vector<int> v : okay){
if(v == seen){
last = r;
return r;
}
}
return -1;
}
}
}
}
int move_bfs(vector<int> y){
if(last >= 0){
y[last]++;
}
for(int r = 0; r < 3; r++){
if(y[r] && y[(r+1)%3]){
assert(last != r);
last = r;
return last;
}
}
int r = 0;
while(y[r] == 0) r++;
assert(last != r);
last = r;
return r;
}
int move(vector<int> y){
if(b == 0){
return move_bfs(y);
} else {
return move_tree(y);
}
}
} // namespace
void Init(int A, int B) {
init(A, B);
}
int Move(std::vector<int> y) {
return move(y);
}
