#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int n, m;
vector <int> ls[N], sol;
int cnt[N], par[N], bio[N];
void dfs(int node, int rod) {
cnt[node]=1;
par[node]=rod;
for (int sus:ls[node]) {
if (sus==par[node]) continue;
dfs(sus, node);
cnt[node]+=cnt[sus];
}
}
int nadji(int node, int a, int b) {
if (cnt[node]>=a && n-cnt[node]>=b) return node;
for (int sus:ls[node]) {
if (sus==par[node]) continue;
int ret=nadji(sus, a, b);
if (ret!=-1) return ret;
}
return -1;
}
int uk;
void oznaci(int node, int ozn) {
if (uk==0) return;
sol[node]=ozn; uk--;
bio[node]=1;
for (int sus:ls[node]) {
if (bio[sus]) continue;
oznaci(sus, ozn);
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
n=nn; m=p.size();
sol.resize(n, 0);
for (int i=0; i<m; ++i) {
ls[p[i]].pb(q[i]);
ls[q[i]].pb(p[i]);
}
vector <pii> mi={{a, 1}, {b, 2}, {c, 3}};
sort(mi.begin(), mi.end());
if (m==n-1) {
dfs(0, -1);
for (int e=0; e<2; ++e) {
int node=nadji(0, mi[0].X, mi[1].X);
if (node!=-1) {
uk=mi[0].X; bio[par[node]]=1; oznaci(node, mi[0].Y);
uk=mi[1].X; bio[par[node]]=0; oznaci(par[node], mi[1].Y);
for (int i=0; i<n; ++i) if (!sol[i]) sol[i]=mi[2].Y;
return sol;
}
swap(mi[0], mi[1]);
}
}
else {
uk=mi[1].X; oznaci(0, mi[1].Y);
for (int i=0; i<n; ++i) {
if (!bio[i]) {
uk=mi[0].X;
oznaci(i, mi[0].Y);
break;
}
}
for (int i=0; i<n; ++i) if (!sol[i]) sol[i]=mi[2].Y;
}
return sol;
}
