#include<bits/stdc++.h>
#include "split.h"
using namespace std;
const int N = 1e5 + 7;
int ti;
int in[N];
int used[N];
vector<int> g[N];
vector<int> t;
void dfs(int v){
used[v] = 1;
in[v] = ++ ti;
t.push_back(v);
for(auto to: g[v]){
if(used[to] == 0) dfs(to);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
map<pair<int, int>, int> used;
for(int i = 0; i < (int)p.size(); i ++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
used[{p[i], q[i]}] = used[{q[i], p[i]}] = 1;
}
int start = 0;
for(int i = 0; i < n; i ++){
if((int)g[i].size() == 1) start = i;
}
dfs(start);
vector<int> g1[4];
vector<int> res(n);
for(int i = 0; i < (int)t.size(); i ++){
if(a --> 0){
res[t[i]] = 1;
g1[1].push_back(t[i]);
}
else if(b --> 0){
res[t[i]] = 2;
g1[2].push_back(t[i]);
}
else if(c --> 0){
res[t[i]] = 3;
g1[3].push_back(t[i]);
}
}
for(int i = 1; i <= 3; i ++){
sort(g1[i].begin(), g1[i].end(), [](int x, int y){
return (in[x] < in[y]);
});
}
for(int i = 1; i <= 3; i ++){
for(int j = 1; j < (int)g1[i].size(); j ++){
int v = g1[i][j - 1];
int to = g1[i][j];
if(used[{v, to}] == 0){
return vector<int>(n, 0);
}
}
}
return res;
}
