#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> haha[100001];
vector<bool> bruh(200001);
vector<bool> troll(200001,1);
vector<int> st(100001);
vector<int> dsu(100001);
vector<int> ans(0);
int n;
int calc(int a) {
int c = a;
while(dsu[c] != c) {
c = dsu[c];
}
int e = a;
while(dsu[e] != e) {
int d = dsu[e];
dsu[e] = c;
e = d;
}
return c;
}
void dfs(int a) {
troll[a] = false;
st[a] = 1;
for(pair<int,int> v: haha[a]) {
if(troll[v.first]) {
bruh[v.second] = 1;
dfs(v.first);
st[a]+=st[v.first];
}
}
}
void dude(int a, int t, int col) {
st[a] = 1;
dsu[a] = col;
for(pair<int,int> v: haha[a]) {
if(bruh[v.second] && v.first != t) {
dude(v.first,a,col);
st[a]+=st[v.first];
}
}
}
int br;
void yo(int a, int t, int z) {
if(br == 0) {
return;
}
br--;
ans[a] = z;
for(pair<int,int> v: haha[a]) {
if(v.first != t && bruh[v.second]) {
yo(v.first,a,z);
}
}
}
void getans(vector<pair<int,int>> wut, int cen, int x) {
for(int i = 0; i < n; i++) {
ans[i] = wut[2].second;
}
br = wut[0].first;
yo(x,cen,wut[0].second);
br = wut[1].first;
yo(cen,x,wut[1].second);
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
ans.resize(n);
for(int i = 0; i < n; i++) {
ans[i] = 0;
}
for(int i = 0; i < n; i++) {
dsu[i] = i;
}
vector<pair<int,int>> wut(0);
wut.push_back({a,1});
wut.push_back({b,2});
wut.push_back({c,3});
sort(wut.begin(),wut.end());
a = wut[0].first;
b = wut[1].first;
int m = p.size();
for(int i = 0; i < m; i++) {
haha[p[i]].push_back({q[i],i});
haha[q[i]].push_back({p[i],i});
}
dfs(0);
int cen = 0;
bool yeah = true;
while(yeah) {
yeah = false;
for(pair<int,int> v: haha[cen]) {
if(bruh[v.second] && st[v.first] < st[cen] && st[v.first]*2 > n) {
cen = v.first;
yeah = true;
break;
}
}
}
vector<int> fedge(n);
for(pair<int,int> v: haha[cen]) {
if(bruh[v.second]) {
dude(v.first,cen,v.first);
fedge[v.first] = v.second;
if(st[v.first] >= a) {
getans(wut,cen,v.first);
return ans;
}
}
}
for(int i = 0; i < m; i++) {
if(p[i] == cen || q[i] == cen) {
continue;
}
int x = calc(p[i]);
int y = calc(q[i]);
if(x != y) {
dsu[y] = x;
st[x]+=st[y];
bruh[fedge[y]] = false;
bruh[i] = true;
if(st[x] >= a) {
getans(wut,cen,x);
return ans;
}
}
}
return ans;
}
