#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename T> istream& operator>>(istream& is, vector<T> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> arr){for (auto &it : arr) os<<it<<" "; return os;}
template<typename T,size_t Y> istream& operator>>(istream& is, array<T,Y> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T,size_t Y> ostream& operator<<(ostream& os, array<T,Y> arr){for (auto &it : arr) os<<it<<" "; return os;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it :x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "split.h"
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> rval(n,0);
int m = p.size();
vector<vector<int>> arr(n);
for (int i = 0; i < m; i++){
arr[p[i]].push_back(q[i]);
arr[q[i]].push_back(p[i]);
}
if (a==1){
function<void(int)> f;
vector<bool> vis(n,false);
int kk = 0;
f = [&](int node)->void{
if (kk==b) return;
vis[node]=true;
rval[node]=2;
kk++;
for (int i = 0; i < arr[node].size(); i++){
if (vis[arr[node][i]]) continue;
f(arr[node][i]);
}
};
f(0);
bool bb = false;
for (int i = 0; i < n; i++){
if (rval[i]) continue;
if (bb) rval[i]=3;
else rval[i]=1,bb=true;
}
return rval;
}
if (m!=n-1) {
fill(rval.begin(), rval.end(), 3);
int node = 0;
vector<bool> vis(n,false);
int kk = 0;
while (true){
kk++;
vis[node]=true;
if (kk<=a) rval[node]=1;
else if (kk<=a+b) rval[node]=2;
else break;
int nex = -1;
for (int i = 0; i < arr[node].size(); i++){
if (vis[arr[node][i]]) continue;
nex=arr[node][i];
break;
}
if (nex==-1) break;
node=nex;
}
return rval;
}
fill(rval.begin(), rval.end(), 0);
array<array<int,2>,3> karr;
karr[0]={a,1};
karr[1]={b,2};
karr[2]={c,3};
sortarr(karr);
a=karr[0][0];
b=karr[1][0];
vector<int> subsz(n);
vector<int> boo(n,-1);
function<void(int,int)> f;
f = [&](int node, int lnode)->void{
subsz[node]=1;
for (int i = 0; i < arr[node].size(); i++){
if (arr[node][i]==lnode) continue;
f(arr[node][i],node);
subsz[node]+=subsz[arr[node][i]];
if (boo[arr[node][i]]!=-1){
if (boo[node]==-1) boo[node]=boo[arr[node][i]];
if (subsz[boo[node]]>subsz[boo[arr[node][i]]]){
boo[node]=boo[arr[node][i]];
}
}
}
if (boo[node]==-1 && subsz[node]>=a) boo[node]=node;
};
int root = 0;
for (int i = 0; i < n; i++){
if (arr[i].size()==1){
root=i;
break;
}
}
f(root,-1);
int k, fil;
function<void(int)> dfs;
bool boolean=false;
dfs = [&](int node)->void{
if (k==0) return;
if (rval[node]!=karr[2][1]) return;
rval[node]=fil;
k--;
for (int i = 0; i < arr[node].size(); i++){
if (subsz[arr[node][i]]>subsz[node] && boolean) continue;
dfs(arr[node][i]);
}
};
int as = boo[root];
if (n-subsz[as]>=b){
fill(rval.begin(), rval.end(), karr[2][1]);
fil = karr[0][1];
k=karr[0][0];
boolean=true;
dfs(as);
boolean=false;
fil = karr[1][1];
k=karr[1][0];
dfs(root);
return rval;
}
return rval;
}
