#include <bits/stdc++.h>
#include "split.h"
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
vector <int> v[N];
int t[N], P[N];
bool f[N];
void dfs(int x, int pr){
P[x] = pr;
t[x] = 1;
for(auto to : v[x])if(to != pr){
dfs(to, x);
t[x] += t[to];
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size(), mx = 0;
for(int i = 0; i < n; i++){
v[i].clear();
t[i] = 0;
}
for(int i = 0; i < m; i++){
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
mx = max(mx, (int)v[p[i]].size());
mx = max(mx, (int)v[q[i]].size());
}
vector <int> res(n);
if(mx < 3){
int F = 0, Last = 0;
for(int i = 0; i < n; i++)if(v[i].size() == 1)F = i;
int step = 1;
vector <int> cnt(3);
cnt[0] = a;
cnt[1] = b;
cnt[2] = c;
for(int i = 0; i < n; i++){
if(i){
int New = 0;
for(auto j : v[F])if(j != Last)New = j;
Last = F;
F = New;
}
while(!cnt[step - 1])step++;
--cnt[step - 1];
res[F] = step;
}
return res;
}else if(a == 1){
queue <int> q;
int start = 0;
q.push(start);
vector <bool> f(n);
f[start] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
if(!b)break;
b--;
res[x] = 2;
for(auto to : v[x])if(!f[to]){
f[to] = 1;
q.push(to);
}
}
for(int i = 0; i < n; i++)if(res[i] == 0){res[i] = 1; break;}
for(int i = 0; i < n; i++)if(res[i] == 0)res[i] = 3;
return res;
}else{
int start = 0;
for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
vector <int> cnt(3);
cnt[0] = a;
cnt[1] = b;
cnt[2] = c;
vector <int> p(3);
p[0] = 1;
p[1] = 2;
p[2] = 3;
for(int i = 0; i < 3; i++)
for(int j = i + 1; j < 3; j++)if(cnt[p[i] - 1] > cnt[p[j] - 1])swap(p[i], p[j]);
dfs(start, -1);
for(int i = 0; i < n; i++)if(t[i] >= cnt[p[1] - 1] && n - t[i] >= cnt[p[0] - 1]){
queue <int> q;
f[i] = 1;
f[P[i]] = 1;
res[P[i]] = p[0];
cnt[p[0] - 1]--;
q.push(P[i]);
while(!q.empty()){
int x = q.front();
q.pop();
res[x] = p[0];
for(auto to : v[x])if(!f[to] && cnt[p[0] - 1]){
cnt[p[0] - 1]--;
f[to] = 1;
q.push(to);
}
}
res[i] = p[1];
cnt[p[1] - 1]--;
q.push(i);
while(!q.empty()){
int x = q.front();
q.pop();
res[x] = p[1];
for(auto to : v[x])if(!f[to] && cnt[p[1] - 1]){
cnt[p[1] - 1]--;
f[to] = 1;
q.push(to);
}
}
for(auto &j : res)if(j == 0)j = p[2];
return res;
}
swap(p[0], p[1]);
for(int i = 0; i < n; i++)if(t[i] >= cnt[p[1] - 1] && n - t[i] >= cnt[p[0] - 1]){
queue <int> q;
f[i] = 1;
f[P[i]] = 1;
res[P[i]] = p[0];
cnt[p[0] - 1]--;
q.push(P[i]);
while(!q.empty()){
int x = q.front();
q.pop();
res[x] = p[0];
for(auto to : v[x])if(!f[to] && cnt[p[0] - 1]){
cnt[p[0] - 1]--;
f[to] = 1;
q.push(to);
}
}
res[i] = p[1];
cnt[p[1] - 1]--;
q.push(i);
while(!q.empty()){
int x = q.front();
q.pop();
res[x] = p[1];
for(auto to : v[x])if(!f[to] && cnt[p[1] - 1]){
cnt[p[1] - 1]--;
f[to] = 1;
q.push(to);
}
}
for(auto &j : res)if(j == 0)j = p[2];
return res;
}
return res;
}
return res;
}
