#include "split.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
ll n, f, z, sz[100000], D[100000], P[100000], back[100000];
vector <ll> adj[100000], E[100000], opt;
bool visited[100000], X[100000];
vector <int> F;
array<ll, 2> A[3];
void dfs_tree(ll u) {
visited[u] = 1;
for (auto v : adj[u]) {
if (!visited[v]) {
P[v] = u;
E[u].push_back(v);
D[v] = D[u] + 1;
dfs_tree(v);
}
else back[u] = min(back[u], D[v]);
}
}
void dfs_sz(ll u) {
sz[u] = 1;
for (auto v : E[u]) {
dfs_sz(v);
back[u] = min(back[u], back[v]);
sz[u] += sz[v];
}
if (A[0][0] <= sz[u] && sz[u] <= n-A[0][0]) f = u;
ll tot = sz[u];
vector <ll> tmp;
for (auto v : E[u]) {
if (back[v] < D[u]) {
tmp.push_back(v);
tot -= sz[v];
if (z == -1 && A[0][0] <= tot && tot <= n-A[0][0]) {
z = u;
opt = tmp;
break;
}
}
}
}
void paint(ll u, ll id) {
if (A[id][0]) {
--A[id][0];
F[u] = A[id][1];
}
for (auto v : E[u]) {
paint(v, id);
}
}
void solve(ll u, ll id) {
if (A[id][0] && F[u] == A[2][1]) {
--A[id][0];
F[u] = A[id][1];
}
for (auto v : adj[u]) {
if (!A[id][0]) return;
if (F[v] == A[2][1]) solve(v, id);
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n = _n, f = z = -1;
A[0] = {a, 1}, A[1] = {b, 2}, A[2] = {c, 3};
sort(A, A+3);
for (int i=0; i<n; ++i) {
X[i] = 0;
back[i] = 1e18;
adj[i].clear();
E[i].clear();
F.push_back(A[2][1]);
visited[i] = 0;
}
for (int i=0; i<p.size(); ++i) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs_tree(0);
dfs_sz(0);
if (f != -1) {
if (A[0][0] <= sz[f] && sz[f] <= n-A[1][0]) {
paint(f, 0);
solve(P[f], 1);
}
else {
paint(f, 1);
solve(P[f], 0);
}
}
else if (z != -1) {
ll tot = sz[z];
for (auto u : opt) tot -= sz[u], X[u] = 1;
if (A[0][0] <= tot && tot <= n-A[1][0]) {
F[z] = A[0][1];
--A[0][0];
for (auto v : E[z]) {
if (!X[v]) paint(v, 0);
}
for (auto v : E[z]) {
if (X[v]) solve(v, 1);
}
}
else {
F[z] = A[1][1];
--A[1][0];
for (auto v : E[z]) {
if (!X[v]) paint(v, 1);
}
for (auto v : E[z]) {
if (X[v]) solve(v, 0);
}
}
}
else {
for (auto &u : F) u = 0;
}
return F;
}
/*
x > n-a
y < a
n-a-ka > a
*/
