#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) {
ord.push_back(u);
vis[u] = 1;
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
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> 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]);
}
vector<int> cmp[3];
for (int i = 0; i < n; ++i) {
cmp[adj[i].size()].push_back(i);
}
vis.resize(n);
for (int i : cmp[1]) {
if (!vis[i]) {
dfs(i);
split();
if (ord.size()) {
return vector<int>(n, 0);
}
}
}
for (int i : cmp[2]) {
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;
}
