#include <bits/stdc++.h>
#include "split.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 100100;
vector<int> res;
vector<int> g[N], vc;
bool mrk[N];
int siz[N], mem, pr[N], col, A[3], C[3];
void dfs(int v){
if (mrk[v]) return;
mrk[v] = 1;
vc.PB(v);
for (int u : g[v])
dfs(u);
}
void build_sz(int v, int p){
siz[v] = 1;
pr[v] = p;
for (int u : g[v]){
if (u == p) continue;
build_sz(u, v);
siz[v] += siz[u];
}
}
void fill(int v, int p){
if (mem == 0) return;
mem--;
res[v] = col;
for (int u : g[v]){
if (u == p) continue;
fill(u, v);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
res.resize(n);
fill(all(res), 0);
for (int i = 0; i < sz(p); i++){
g[p[i]].PB(q[i]);
g[q[i]].PB(p[i]);
}
if (sz(p) == n - 1){
build_sz(0, -1);
A[0] = a; A[1] = b; A[2] = c;
C[0] = 1; C[1] = 2; C[2] = 3;
for (int v = 0; v < n; v++){
int sub = siz[v], up = n - siz[v];
bool was = 0;
for (int i = 0; i < 3 && !was; i++)
for (int j = 0; j < 3 && !was; j++)
if (i != j && A[i] <= sub && A[j] <= up){
was = 1;
mem = A[i]; col = C[i];
fill(v, pr[v]);
mem = A[j]; col = C[j];
fill(pr[v], v);
if (C[i] != 1 && C[j] != 1) col = 1;
if (C[i] != 2 && C[j] != 2) col = 2;
if (C[i] != 3 && C[j] != 3) col = 3;
for (int &cr : res)
if (cr == 0)
cr = col;
break;
}
if (was) break;
}
return res;
}
bool was = 0;
for (int i = 0; i < n; i++)
if (sz(g[i]) == 1){
was = 1;
dfs(i);
break;
}
if (!was) dfs(0);
for (int i = 0; i < a; i++)
res[vc[i]] = 1;
for (int i = 0; i < b; i++)
res[vc[a + i]] = 2;
for (int i = 0; i < c; i++)
res[vc[a + b + i]] = 3;
return res;
}
