#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int a_, int b_, int c_, vector<int> pp, vector<int> q) {
vector<int> res(n);
vector<pair<int,int>> pts = {{a_, 1}, {b_, 2}, {c_, 3}};
sort(pts.begin(), pts.end());
int m = (int) pp.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
g[pp[i]].push_back(q[i]);
g[q[i]].push_back(pp[i]);
}
auto [s, c] = pts[0];
vector<bool> vis(n);
function<void(int)> Dfs = [&](int v) {
--s;
res[v] = c;
vis[v] = true;
for (int u : g[v]) {
if (!s) return;
if (!vis[u]) Dfs(u);
}
};
int start = 0;
for (int i = 1; i < n; ++i) {
if (g[i].size() == 1) {
start = i;
break;
}
}
Dfs(start);
s = pts[1].first;
c = pts[1].second;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
Dfs(i);
break;
}
}
for (int i = 0; i < n; ++i) {
if (!res[i]) {
res[i] = pts[2].second;
}
}
return res;
}
