#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
int n, m;
vector<int> ord, k, ans;
void dfs (int u) {
vis[u] = 1;
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v);
}
}
ord.push_back(u);
}
void go (int i) {
while (k[i]) {
--k[i];
ans[ord.back()] = i + 1;
ord.pop_back();
}
}
void split () {
if ((int)ord.size() == k[0] + k[1] + k[2]) {
go(0);
go(1);
go(2);
}
for (int i = 0; i < 3; ++i) {
for (int j = i + 1; j < 3; ++j) {
if (k[i] + k[j] == (int)ord.size()) {
go(i);
go(j);
}
}
}
for (int i = 0; i < 3; ++i) {
if ((int)ord.size() == k[i]) {
go(i);
}
}
}
vector<int> sub;
void color (int u, int c, int p, int f = -1) {
ans[u] = c;
for (int v : adj[u]) {
if (v ^ p && v ^ f) {
color(v, c, u);
}
}
}
void dfs2 (int u, int p = -1) {
sub[u] = 1;
vis[u] = 1;
for (int v : adj[u]) {
if (!vis[v]) {
dfs2(v, u);
}
if (v ^ p) {
sub[u] += sub[v];
}
}
auto i = find(k.begin(), k.end(), sub[u]);
if (i != k.end()) {
color(u, i - k.begin() + 1, p);
*i = 0;
if (~p) {
adj[p].erase(find(adj[p].begin(), adj[p].end(), u));
}
sub[u] = 0;
return;
}
for (int v : adj[u]) {
if (v == p) continue;
i = find(k.begin(), k.end(), sub[u] - sub[v]);
if (i != k.end()) {
color(u, i - k.begin() + 1, p, v);
*i = 0;
if (~p) {
adj[p].erase(find(adj[p].begin(), adj[p].end(), u));
}
sub[u] = 0;
return;
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
::n = n;
k = {a, b, c};
m = p.size();
adj.resize(n);
ans.resize(n);
for (int i = 0; i < m; ++i) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vis.resize(n);
if (m == n - 1) {
sub.resize(n);
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs2(i);
}
if (!ans[i]) {
ord.push_back(i);
}
}
split();
if (ord.size()) {
return vector<int>(n, 0);
}
return ans;
}
vector<int> cmp[m + 1];
for (int i = 0; i < n; ++i) {
cmp[adj[i].size()].push_back(i);
}
for (int j = 1; j <= m; ++j) {
for (int i : cmp[j]) {
if (!vis[i]) {
dfs(i);
split();
if (ord.size()) {
return vector<int>(n, 0);
}
}
}
}
if (count(k.begin(), k.end(), 0) < 2) {
return vector<int>(n, 0);
}
ord = cmp[0];
split();
if (ord.size()) {
return vector<int>(n, 0);
}
return ans;
}
