#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi19/d1/debug.h"
#else
#define debug(...) void(37)
#endif
struct DSU {
vector<int> link;
DSU(int n) {
link.resize(n);
iota(link.begin(), link.end(), 0);
}
int get(int v) {
return link[v] = (v == link[v] ? v : get(link[v]));
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) {
return false;
}
link[y] = x;
return true;
}
};
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
array<array<int, 2>, 3> ord{};
ord[0] = {A, 1};
ord[1] = {B, 2};
ord[2] = {C, 3};
sort(ord.begin(), ord.end());
vector<vector<int>> g(N);
int M = int(P.size());
for (int i = 0; i < M; ++i) {
g[P[i]].push_back(Q[i]);
g[Q[i]].push_back(P[i]);
}
auto Build = [&](int root, vector<vector<int>>& dfs_g) {
vector<int> size(N, 1);
vector<bool> vis(N);
vector<int> from(N, -1);
vector<vector<int>> tree(N);
function<void(int)> Dfs = [&](int v) {
vis[v] = true;
for (auto u : dfs_g[v]) {
if (!vis[u]) {
from[u] = (from[v] == -1 ? u : from[v]);
Dfs(u);
tree[v].push_back(u);
tree[u].push_back(v);
size[v] += size[u];
}
}
};
Dfs(root);
return make_tuple(tree, size, from);
};
auto[tree, size, from] = Build(0, g);
debug(tree, size, from);
int lower = N / 3;
//int lower = ord[0][0];
int upper = N - lower;
int root = 0;
while (true) {
int go = -1;
for (auto u : tree[root]) {
if (size[u] > upper) {
go = u;
}
}
if (go == -1) {
break;
}
size[root] = N - size[go];
size[go] = N;
root = go;
}
tie(tree, size, from) = Build(root, tree);
debug(root, size, from);
for (auto u : tree[root]) {
assert(size[u] <= upper);
}
DSU group(N);
for (int i = 0; i < M; ++i) {
if (from[P[i]] != -1 && from[Q[i]] != -1) {
group.unite(from[P[i]], from[Q[i]]);
}
}
vector<int> tot(N);
for (auto u : tree[root]) {
tot[group.get(u)] += size[u];
}
int use = int(max_element(tot.begin(), tot.end()) - tot.begin());
debug(use);
if (tot[use] < ord[0][0]) {
return vector<int>(N, 0);
}
vector<bool> take(N);
vector<vector<int>> comp_g(N);
for (int i = 0; i < M; ++i) {
int x = from[P[i]], y = from[Q[i]];
if (x != -1 && y != -1) {
comp_g[x].push_back(y);
comp_g[y].push_back(x);
}
}
int taken = 0;
function<void(int)> Expand = [&](int v) {
take[v] = true;
for (auto u : comp_g[v]) {
if (!take[u] && taken < ord[0][0]) {
taken += size[u];
Expand(u);
}
}
};
Expand(use);
debug(take);
if (taken >= ord[1][0]) {
swap(ord[0], ord[1]);
}
vector<int> ans(N, 3);
function<void(int, int&, int)> Set = [&](int v, int& left, int id) {
--left;
ans[v] = id;
for (auto u : g[v]) {
if (ans[u] == 3 && left > 0) {
Set(u, left, id);
}
}
};
int small = ord[0][0];
for (int i = 0; i < N; ++i) {
if (from[i] != -1 && !take[from[i]]) {
ans[i] = 2;
}
}
Set(use, small, 1);
assert(small <= 0);
for (int i = 0; i < N; ++i) {
if (ans[i] != 1) {
ans[i] = 3;
}
}
int middle = ord[1][0];
Set(root, middle, 2);
assert(middle == 0);
for (int i = 0; i < N; ++i) {
ans[i] = ord[ans[i] - 1][1];
}
return ans;
}
