#include "split.h"
#include <iostream>
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
int inf = 1e9 + 7;
vector<vector<pair<int, int>>> g;
vector<int> used;
vector<int> active;
int cnt;
int B;
void dfs(int v) {
if (cnt == B)
return;
used[v] = 1;
cnt++;
for (auto [u, w] : g[v]) {
if (!active[w])
continue;
if (!used[u]) {
dfs(u);
}
}
}
vector<int> sz;
vector<int> par;
void dfs_sz(int v, int p = -1) {
par[v] = p;
sz[v] = 1;
for (auto [u, w]: g[v]) {
if (!used[u]) {
dfs_sz(u, v);
sz[v] += sz[u];
}
}
}
int centr = 0;
void find_cen(int v, int n) {
bool ok = 1;
for (auto [u, w] : g[v]) {
if (sz[u] > n / 2) {
ok = 0;
find_cen(u, n);
}
}
if (ok)
centr = v;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
g.assign(n, {});
int m = p.size();
active.assign(m, 1);
map<pair<int, int>, int> edg;
for (int i = 0; i < m; i++) {
g[p[i]].push_back({q[i], i});
g[q[i]].push_back({p[i], i});
edg[{p[i], q[i]}] = i;
edg[{q[i], p[i]}] = i;
}
bool two = 1;
int mini = inf, indmi = -1;
for (int i = 0; i < n; i++) {
if (g[i].size() > 2)
two = 0;
if (g[i].size() < mini) {
mini = g[i].size();
indmi = i;
}
}
if (two) {
vector<int> res(n, 3);
res[indmi] = 1;
int last = indmi;
int cur = g[indmi][0].fi;
for (int i = 0; i < a - 1; i++) {
res[cur] = 1;
int tr = cur;
cur = g[cur][0].fi + g[cur][1].fi - last;
last = tr;
}
for (int i = 0; i < b; i++) {
res[cur] = 2;
int tr = cur;
cur = g[cur][0].fi + g[cur][1].fi - last;
last = tr;
}
return res;
} else if (a == 1) {
used.assign(n, 0);
cnt = 0;
B= b;
dfs(0);
vector<int> res(n, 3);
for (int i = 0; i < n; i ++) {
if (used[i])
res[i] = 2;
}
for (int i = 0; i < n; i++) {
if (res[i] == 3) {
res[i] = 1;
break;
}
}
return res;
} else {
used.assign(n, 0);
sz.assign(n, 0);
par.assign(n, 0);
dfs_sz(0);
used.assign(n, 0);
centr = 0;
find_cen(0, n);
int cent = centr;
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
int maxi = n - sz[cent];
int neig = par[cent];
for (auto [u,w] : g[cent]) {
if (u != par[cent]) {
if (maxi < sz[u]) {
maxi = sz[u];
neig = u;
}
}
}
vector<int> res(n, 0);
if (maxi < a) {
return res;
}
for (int i = 0; i < n; i++)
res[i] = 3;
active[edg[{cent, neig}]] = 0;
B = a;
cnt = 0;
used.assign(n, 0);
dfs(neig);
for (int i = 0; i < n; i++) {
if (used[i])
res[i] = 1;
}
B = b;
cnt = 0;
used.assign(n, 0);
dfs(cent);
for (int i = 0; i < n; i++) {
if (used[i])
res[i] = 2;
}
return res;
}
}
/*
signed main() {
int n;
cin >> n;
vector<int> s(2 * n);
for (int i = 0; i < 2 * n; i++) {
cin >> s[i];
}
int res = count_swaps(s);
cout << res << endl;
}
*/
