#include "split.h"
#define pb push_back
using namespace std;
const int nmax = 1e5 + 5;
vector<int> ed[nmax];
bool visited[nmax];
vector<int> ans;
int cur_a = 0, cur_b = 0, cur_c = 0;
void dfs(int v, int a, int b, int c){
if (cur_a != a) ans[v] = 1, cur_a++;
else if (cur_b != b) ans[v] = 2, cur_b++;
else ans[v] = 3, cur_c++;
visited[v] = true;
for (auto to : ed[v]){
if (!visited[to]) dfs(to, a, b, c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
ans.resize(n);
vector<int> deg(n);
int m = p.size();
for (int i = 0; i < m; ++i) {
ed[p[i]].pb(q[i]);
ed[q[i]].pb(p[i]);
deg[p[i]]++;
deg[q[i]]++;
}
int mni = 0;
for (int i = 1; i < n; ++i) {
if (deg[i] < deg[mni]) mni = i;
}
dfs(mni, a, b, c);
return ans;
}
