#include "split.h"
#include <bits/stdc++.h>
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
auto start_t = clock();
std::vector<int> res(n);
std::vector<int> connections[n];
for (int i = 0; i < p.size(); ++i) {
connections[p[i]].push_back(q[i]);
connections[q[i]].push_back(p[i]);
}
bool s1 = true;
for (int i = 0; i < n; ++i) {
if (connections[i].size() > 2) s1 = false;
}
if (s1) {
int start = 0;
for (int i = 0; i < n; ++i) {
if (connections[i].size() == 1) {
start = i;
break;
}
}
std::vector<int> order;
while (order.size() < n) {
order.push_back(start);
int next = connections[start][0];
if (connections[next].size() == 2 && connections[next][0] == start) {
std::swap(connections[next][0], connections[next][1]);
}
start = next;
}
for (int i = 0; i < a; ++i) {
res[order[i]] = 1;
}
for (int i = a; i < a + b; ++i) {
res[order[i]] = 2;
}
for (int i = a + b; i < n; ++i) {
res[order[i]] = 3;
}
} else if (a == 1) {
std::queue<int> bfs;
bfs.push(0);
res[0] = 2;
int rem = b - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto x: connections[next]) {
if (!rem) break;
if (res[x]) continue;
res[x] = 2;
bfs.push(x);
rem--;
}
}
for (int i = 0; i < n; ++i) {
if (res[i] == 0) {
res[i] = 1;
break;
}
}
for (int i = 0; i < n; ++i) {
if (res[i] == 0) res[i] = 3;
}
} else if (p.size() == n - 1) {
int size[n];
int parent[n];
std::vector<int> children[n];
std::function<int(int, int)> dfs = [&](int node, int from) {
parent[node] = from;
int res = 1;
for (auto x: connections[node]) {
if (x == from) continue;
children[node].push_back(x);
res += dfs(x, node);
}
return size[node] = res;
};
dfs(0, 0);
std::function<int(int, int, int)> fill = [&](int node, int num, int type) {
if (num == 0) return 0;
num--;
res[node] = type;
for (auto x: children[node]) {
num = fill(x, num, type);
}
return num;
};
std::function<void(int, int, int)> expand = [&](int node, int num, int type) {
std::queue<int> bfs;
bfs.push(node);
res[node] = type;
int rem = num - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto x: connections[next]) {
if (!rem) break;
if (res[x]) continue;
res[x] = type;
bfs.push(x);
rem--;
}
}
};
std::function<void(int)> fix = [&](int type) {
for (int i = 0; i < n; ++i) {
if (res[i] == 0) res[i] = type;
}
};
for (int i = 0; i < n; ++i) {
int s = size[i];
int so = n - size[i];
if (s >= a) {
if (so >= b) {
fill(i, a, 1);
expand(parent[i], b, 2);
fix(3);
return res;
}
if (so > c) {
fill(i, a, 1);
expand(parent[i], c, 3);
fix(2);
return res;
}
}
if (s >= b) {
if (so >= a) {
fill(i, b, 2);
expand(parent[i], a, 1);
fix(3);
return res;
}
if (so > c) {
fill(i, b, 2);
expand(parent[i], c, 3);
fix(1);
return res;
}
}
if (s >= c) {
if (so >= b) {
fill(i, c, 3);
expand(parent[i], b, 2);
fix(1);
return res;
}
if (so > a) {
fill(i, c, 3);
expand(parent[i], a, 1);
fix(2);
return res;
}
}
}
} else {
std::mt19937 Rand(std::random_device{}());
std::uniform_int_distribution dist(0, n - 1);
while (clock() - start_t <= 1.9 * CLOCKS_PER_SEC) {
int root = dist(Rand);
for (int i = 0; i < n; ++i) {
std::shuffle(connections[i].begin(), connections[i].end(), std::default_random_engine(Rand()));
}
int size[n];
int parent[n];
std::vector<int> children[n];
bool seen[n];
for (int i = 0; i < n; ++i) {
seen[i] = false;
}
std::function<void(int)> Root = [&](int node) {
parent[node] = node;
seen[node] = true;
if (Rand() % 2) {
std::queue<int> queue;
queue.push(node);
while (!queue.empty()) {
auto next = queue.front();
queue.pop();
for (auto x: connections[next]) {
if (seen[x]) continue;
seen[x] = true;
parent[x] = next;
children[next].push_back(x);
queue.push(x);
}
}
} else {
std::stack<int> queue;
queue.push(node);
while (!queue.empty()) {
auto next = queue.top();
queue.pop();
for (auto x: connections[next]) {
if (seen[x]) continue;
seen[x] = true;
parent[x] = next;
children[next].push_back(x);
queue.push(x);
}
}
}
// seen[node] = true;
// parent[node] = from;
// int res = 1;
// for (auto x: connections[node]) {
// if (seen[x]) continue;
// children[node].push_back(x);
// res += dfs(x, node);
// }
// return size[node] = res;
};
std::function<int(int, int)> oldroot = [&](int node, int from) {
seen[node] = true;
parent[node] = from;
int res = 1;
for (auto x: connections[node]) {
if (seen[x]) continue;
children[node].push_back(x);
res += oldroot(x, node);
}
return size[node] = res;
};
std::function<int(int)> dfs = [&](int node) {
int s = 1;
for (auto x: children[node]) {
s += dfs(x);
}
return size[node] = s;
};
if (Rand() % 2) {
Root(root);
dfs(root);
} else {
oldroot(root, root);
}
std::function<int(int, int, int)> fill = [&](int node, int num, int type) {
if (num == 0) return 0;
num--;
res[node] = type;
for (auto x: children[node]) {
num = fill(x, num, type);
}
return num;
};
std::function<void(int, int, int)> expand = [&](int node, int num, int type) {
std::queue<int> bfs;
bfs.push(node);
res[node] = type;
int rem = num - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto x: connections[next]) {
if (!rem) break;
if (res[x]) continue;
res[x] = type;
bfs.push(x);
rem--;
}
}
};
std::function<void(int)> fix = [&](int type) {
for (int i = 0; i < n; ++i) {
if (res[i] == 0) res[i] = type;
}
};
for (int i = 0; i < n; ++i) {
int s = size[i];
int so = n - size[i];
if (s >= a) {
if (so >= b) {
fill(i, a, 1);
expand(parent[i], b, 2);
fix(3);
return res;
}
if (so > c) {
fill(i, a, 1);
expand(parent[i], c, 3);
fix(2);
return res;
}
}
if (s >= b) {
if (so >= a) {
fill(i, b, 2);
expand(parent[i], a, 1);
fix(3);
return res;
}
if (so > c) {
fill(i, b, 2);
expand(parent[i], c, 3);
fix(1);
return res;
}
}
if (s >= c) {
if (so >= b) {
fill(i, c, 3);
expand(parent[i], b, 2);
fix(1);
return res;
}
if (so > a) {
fill(i, c, 3);
expand(parent[i], a, 1);
fix(2);
return res;
}
}
}
}
}
return res;
}
