#include <queue>
#include <string>
#include <vector>
namespace {
std::string s = "110100";
std::vector<int> graph(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
std::vector<int> x(M, -1);
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
std::vector<bool> vis(N);
std::vector<int> dep(N);
std::queue<int> q;
q.push(0);
vis[0] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int &i : adj[u]) {
if (vis[i]) {
continue;
}
vis[i] = true;
dep[i] = dep[u] + 1;
q.push(i);
}
}
for (int i = 0; i < M; ++i) {
x[i] = std::min(dep[U[i]], dep[V[i]]) % 3;
}
return x;
}
std::vector<int> tree(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
std::vector<std::vector<std::pair<int, int>>> adj(N);
for (int i = 0; i < M; ++i) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
std::vector<int> ans(M);
auto dfs = [&](auto &&self, int u, int p, int c, int st) -> void {
if (adj[u].size() != 2) {
if (st != -1) {
st = -1;
}
for (auto &[i, edge_idx] : adj[u]) {
if (i == p) {
continue;
}
ans[edge_idx] = c;
self(self, i, u, !ans[edge_idx], st);
}
return;
}
if (st == -1) {
st = s.find(!c + '0') + 1;
}
st = st % s.length();
for (auto &[i, edge_idx] : adj[u]) {
if (i == p) {
continue;
}
ans[edge_idx] = s[st] - '0';
self(self, i, u, !ans[edge_idx], st + 1);
}
};
dfs(dfs, 0, -1, 0, -1);
return ans;
}
} // namespace
std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
if (A == 2) {
return tree(N, M, A, B, U, V);
}
return graph(N, M, A, B, U, V);
}
#include <algorithm>
#include <string>
#include <vector>
namespace {
int A, B;
std::string corr = "110100";
std::vector<std::string> poss;
int prev = -1;
bool fixed = false;
std::string picked;
int graph(std::vector<int> y) {
std::vector<int> vals;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < y[i]; ++j) {
vals.push_back(i);
}
}
int max = *std::max_element(vals.begin(), vals.end());
int min = *std::min_element(vals.begin(), vals.end());
if (max - min <= 1) {
return min;
}
return max;
}
int tree(std::vector<int> y) {
auto pick = [&](int x) {
picked.push_back((prev = x == -1 ? prev : x) + '0');
return x == -1 ? x : prev;
};
int z = y[0] + (prev == 0), o = y[1] + (prev == 1);
if (y[0] == 0 and y[1] == 0) {
fixed = true;
return pick(-1);
}
auto minority = [&]() {
if (o < z) {
return (o - (prev == 1)) ? 1 : -1;
}
return (z - (prev == 0)) ? 0 : -1;
};
if (z != o and o != 0 and z != 0) {
fixed = true;
return pick(minority());
}
if (fixed) {
return pick((o - (prev == 1)) > (z - (prev == 0)));;
}
if (prev == -1) {
if (o == 0) {
picked.push_back('0');
} else if (z == 0) {
picked.push_back('1');
} else {
picked.push_back((o <= z) + '0');
}
}
int will = pick((o - (prev == 1)) > (z - (prev == 0)));
if (picked.length() == 5) {
fixed = true;
auto it = std::find(poss.begin(), poss.end(), picked);
if (it != poss.end()) {
return pick(-1);
}
}
return will;
}
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
for (int i = 0; i < 6; ++i) {
std::string t;
for (int j = 0; j < 5; ++j) {
t.push_back(corr[(i + j) % 6]);
}
poss.push_back(t);
}
}
int Move(std::vector<int> y) {
if (A == 2) {
return tree(y);
}
return graph(y);
}
