#include "split.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define N_ 201000
using namespace std;
vector<int>E[N_], T[N_], GP[N_], G[N_];
int n, AA, BB, CC, par[N_], vis[N_], C[N_], Where[N_], chk[N_];
void DFS1(int a) {
vis[a] = 1;
C[a] = 1;
for (auto &x : E[a]) {
if (vis[x]) continue;
par[x] = a;
T[a].push_back(x);
T[x].push_back(a);
DFS1(x);
C[a] += C[x];
}
}
int M1=1, M2=2, M3=3;
vector<int>TP;
void DFS2(int a, int pp) {
TP.push_back(a);
for (auto &x : T[a]) {
if (x == pp)continue;
DFS2(x, a);
}
}
void DFS3(int a, int pp, int ppp) {
GP[ppp].push_back(a);
Where[a] = ppp;
C[a] = 1;
for (auto &x : T[a]) {
if (x != pp) {
DFS3(x, a, ppp);
C[a] += C[x];
}
}
}
int val[N_], szlim;
void DFS4(int a){
vis[a] = 1;
if (szlim) {
TP.push_back(a);
szlim--;
}
for (auto &x : E[a]) {
if (val[x] && !vis[x])DFS4(x);
}
}
vector<int>Conn(vector<int> A, int num) {
int i;
for (i = 1; i <= n; i++)val[i] = 0, vis[i] = 0;
for (auto &x : A)val[x] = 1;
TP.clear();
szlim = num;
DFS4(A[0]);
return TP;
}
vector<int> Remaining(vector<int> A) {
int i;
for (i = 1; i <= n; i++)vis[i] = 0;
for (auto &x : A)vis[x] = 1;
vector<int>res;
for (i = 1; i <= n; i++)if (!vis[i])res.push_back(i);
return res;
}
vector<int>MakeAns(vector<int>A, vector<int>B) {
if (A.size() > B.size()) {
swap(A, B);
}
A = Conn(A, AA);
B = Conn(B, BB);
vector<int>res(n);
for (int i = 0; i < n; i++)res[i] = M3;
for (auto &x : A)res[x-1] = M1;
for (auto &x : B)res[x-1] = M2;
return res;
}
int sum;
void Go(int a) {
vis[a] = 1;
TP.push_back(a);
sum += C[a];
if (sum >= AA)return;
for (auto &x : G[a]) {
if (!vis[x]) {
Go(x);
if (sum >= AA)return;
}
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
if (a > b)swap(a, b),swap(M1,M2);
if (a > c)swap(a, c),swap(M1,M3);
if (b > c)swap(b, c),swap(M2,M3);
AA = a, BB = b, CC = c;
int i;
for (i = 0; i < p.size(); i++) {
E[p[i]+1].push_back(q[i]+1);
E[q[i]+1].push_back(p[i]+1);
}
DFS1(1);
for (i = 1; i <= n; i++) {
if ((C[i] >= AA && n - C[i] >= BB)|| (C[i] >= BB && n - C[i] >= AA)) {
TP.clear();
DFS2(i, par[i]);
vector<int>TP2 = Remaining(TP);
return MakeAns(TP, TP2);
}
}
int Mn = 1e9, mid = -1;
for (i = 1; i <= n; i++) {
if (Mn > C[i] && C[i] * 2 > n)Mn = C[i], mid = i;
}
for (auto &x : T[mid]) {
chk[x] = 1;
DFS3(x, mid, x);
}
for (i = 1; i <= n; i++) {
for (auto &x : E[i]) {
if (i == mid || x == mid)continue;
if (Where[i] != Where[x]) {
G[Where[i]].push_back(Where[x]);
}
}
}
for (i = 1; i <= n; i++)vis[i] = 0;
for (auto &t : T[mid]) {
sum = 0;
TP.clear();
Go(T[mid][0]);
if (sum >= AA) {
vector<int>TT;
for (auto &tt : TP) {
for (auto &x : GP[tt]) {
TT.push_back(x);
}
}
return MakeAns(TT, Remaining(TT));
}
}
vector<int>res(n);
return res;
}
