#include "Anthony.h"
#include <queue>
#include <string>
#include <vector>
namespace {
std::string s = "110100";
}
std::vector<int> Mark(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 we're not a degree 2, make sure to color alternatingly
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]) { // should only run for one node cuz we skip parent
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;
}
#include "Catherine.h"
#include <algorithm>
#include <cassert>
#include <iostream>
#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;
} // 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 < 6; ++j) {
t.push_back(corr[(i + j) % 6]);
}
poss.push_back(t);
}
}
int Move(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 we're at a leaf then just return -1 and claim fixed
if (y[0] == 0 and y[1] == 0) {
fixed = true;
return pick(-1);
}
// we're guranteed o+z != 0
auto minority = [&]() {
if (o < z) {
return (o - (prev == 1)) ? 1 : -1;
}
return (z - (prev == 0)) ? 0 : -1;
};
// if we can, choose minority
if (z != o and o != 0 and z != 0) {
fixed = true;
return pick(minority());
}
// now we're sure all counts are equal
// so we're at a deg=2
// but if we're already fixed, we can just pick the only (parent) edge
if (fixed) {
return pick((o - (prev == 1)) > (z - (prev == 0)));
}
// not fixed and deg 2
// so we either fix it the next time we land up here or it fixes itself by encountering deg!=2
// fix it
if (picked.length() == 6) {
fixed = true;
auto it = std::find(poss.begin(), poss.end(), picked);
if (it != poss.end()) { // we're going away from the root
return pick(-1);
}
}
return pick((o - (prev == 1)) > (z - (prev == 0))); // either fixed pick, so its fine, or random pick if prev is -1
}
