#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
vector<P> edge;
vector<int> tree[1000005];
int ind[3];
int p[1000005];
int sz[1000005];
vector<int> ret;
int find(int a) {
return p[a]<0?a:p[a]=find(p[a]);
}
void merge(int a,int b) {
a=find(a);
b=find(b);
if (a!=b) {
p[a]+=p[b];
p[b]=a;
}
}
void get_sz(int v,int pr) {
sz[v]=1;
for(int nt:tree[v]) {
if (nt!=pr) {
get_sz(nt,v);
sz[v]+=sz[nt];
}
}
}
int get_cent(int v,int pr,int half) {
for(int nt:tree[v]) {
if (nt==pr) {
continue;
}
if (sz[nt]>half) {
return get_cent(nt,v,half);
}
}
return v;
}
bool vis[1000005];
bool vis1[1000005];
void bfs0(int v,int pr,int k,int x) {
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(v);
vis[v]=true;
for(int i=0;i<k;i++) {
int now=q.front();
q.pop();
ret[now]=x;
for(int nt:tree[now]) {
if (nt!=pr&&!vis[nt]) {
q.push(nt);
vis[nt]=true;
}
}
}
}
int type[1000005];
void dfs_type(int v,int pr,int x) {
type[v]=x;
for(int nt:tree[v]) {
if (nt!=pr) {
dfs_type(nt,v,x);
}
}
}
vector<int> adj[1000005];
vector<int> adj1[1000005];
void bfs1(int v,int k,int x) {
queue<int> q;
q.push(v);
memset(vis1,0,sizeof(vis1));
vis1[v]=true;
for(int i=0;i<k;i++) {
int now=q.front();
q.pop();
ret[now]=x;
for(int nt:adj[now]) {
if (vis[type[nt]]&&!vis1[nt]) {
q.push(nt);
vis1[nt]=true;
}
}
}
}
void bfs2(int v,int k,int x) {
queue<int> q;
q.push(v);
memset(vis1,0,sizeof(vis1));
vis1[v]=true;
for(int i=0;i<k;i++) {
int now=q.front();
q.pop();
ret[now]=x;
for(int nt:adj[now]) {
if (!vis[type[nt]]&&!vis1[nt]) {
q.push(nt);
vis1[nt]=true;
}
}
}
}
vector<int> vec;
queue<int> q;
vector<int> find_split(int n, int a, int b, int c, vector<int> pp, vector<int> qq) {
for(int i=0;i<3;i++) {
ind[i]=i+1;
}
if (b>c) {
swap(b,c);
swap(ind[1],ind[2]);
}
if (a>b) {
swap(a,b);
swap(ind[0],ind[1]);
}
if (b>c) {
swap(b,c);
swap(ind[1],ind[2]);
}
ret.resize(n);
for(int i=0;i<n;i++) {
ret[i]=ind[2];
}
for(int i=0;i<pp.size();i++) {
adj[pp[i]].push_back(qq[i]);
adj[qq[i]].push_back(pp[i]);
edge.push_back(P(pp[i],qq[i]));
}
memset(p,-1,sizeof(p));
for(P x:edge) {
if (find(x.first)!=find(x.second)) {
merge(x.first,x.second);
tree[x.first].push_back(x.second);
tree[x.second].push_back(x.first);
}
}
get_sz(0,-1);
int ct=get_cent(0,-1,n/2);
get_sz(ct,-1);
type[ct]=ct;
for(int nt:tree[ct]) {
if (sz[nt]>=a) {
bfs0(nt,ct,a,ind[0]);
bfs0(ct,nt,b,ind[1]);
return ret;
}
dfs_type(nt,ct,nt);
}
memset(vis,0,sizeof(vis));
for(P x:edge) {
if (x.first==ct||x.second==ct) {
continue;
}
if (type[x.first]!=type[x.second]) {
adj1[type[x.first]].push_back(type[x.second]);
adj1[type[x.second]].push_back(type[x.first]);
}
}
memset(vis,0,sizeof(vis));
for(int nxt:tree[ct]) {
if (vis1[nxt]) {
continue;
}
q.push(nxt);
vis[nxt]=true;
int x=0;
while (!q.empty()) {
int now=q.front();
vec.push_back(now);
q.pop();
x+=sz[now];
if (x>=a) {
if (x<=n/2) {
bfs1(now,a,ind[0]);
bfs2(ct,b,ind[1]);
}
else {
bfs1(now,b,ind[1]);
bfs2(ct,a,ind[0]);
}
return ret;
}
for(int nt:adj1[now]) {
if (!vis[nt]) {
vis[nt]=true;
q.push(nt);
}
}
}
for(int x:vec) {
vis[x]=false;
vis1[x]=true;
}
vec.clear();
}
for(int i=0;i<n;i++) {
ret[i]=0;
}
return ret;
}
