#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ll> adj[100005];
ll siz[5], lab[5];
ll sub[100005], status[100005];
ll find_centroid(ll x = 0)
{
//show(x);
sub[x] = 1;
status[x] = 0;
for (ll u: adj[x]) if (status[u]==-1)
{
ll res = find_centroid(u);
sub[x] += sub[u];
if (sub[u] >= siz[0]) return res;
}
status[x] = 1;
//show(sub[x]);
return x;
}
void paint(ll x, ll prevv, ll neww)
{
if (siz[neww]==0) return;
//show3(x, prevv, neww);
//show(siz[neww]);
siz[neww]--;
status[x] = lab[neww];
for (ll u: adj[x]) if (status[u]==prevv) paint(u, prevv, neww);
}
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q)
{
for (ll i=0; i<n; ++i) adj[i].clear();
vector<int> ans(n, 0);
siz[0] = a, siz[1] = b, siz[2] = c, siz[3] = n;
lab[0] = 1, lab[1] = 2, lab[2] = 3, lab[3] = 4;
for (ll i=0; i<2; ++i) {if (siz[i] > siz[i + 1]) {swap(siz[i], siz[i + 1]); swap(lab[i], lab[i + 1]);}}
for (ll i=1; i>=0; --i) {if (siz[i] > siz[i + 1]) {swap(siz[i], siz[i + 1]); swap(lab[i], lab[i + 1]);}}
for (ll i=0; i<p.size(); ++i)
{
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
//show(1);
fill(status, status+ n, -1);
ll root = find_centroid();
//show(root);
if (root!=0)
{
// paint subtree >= a
paint(root, 1, 3);
if (sub[root] >= siz[1]) {swap(siz[0], siz[1]); swap(lab[0], lab[1]);}
// subtree of root -> 4, otheriwse 5
for (ll i=0; i<n; ++i) status[i] = ((status[i]==4)?4: 5);
//for (ll i=0; i<n; ++i) show2(i, status[i]);
// paint subtree outside as 1
paint(0, 5, 1);
// add more edges to 1 (if needed) through any backedge
status[root] = 69;
for (ll i=0; i<n; ++i) if (status[i]==lab[1]) for (ll u: adj[i]) if (status[u]==4) paint(u, 4, 1);
// confirm leftover for subtree 0
status[root] = 4;
paint(root, 4, 0);
//for (ll i=0; i<n; ++i) show(status[i]);
}
//show2(lab[0], lab[1]);
//show2(siz[0], siz[1]);
if (siz[0] != 0 || siz[1]!= 0) return ans;
for (ll i=0; i<n; ++i) ans[i] = ((status[i]<=3)?status[i]:lab[2]);
return ans;
}
