#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x)
#define p2(x,y)
#define pp(x)
#define pv(x)
#define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;
vector<vector<int> > adj(N);
vector<int> res;
bool v[N];
pi siz[3];
int cnt[N];
int par[N];
void dfs(int s, int e){
par[s] = e;
cnt[s] = 1;
for(auto x : adj[s])
if(x!=e && res[x]==0){
dfs(x,s);
cnt[s] += cnt[x];
}
}
int curr;
int now;
void color(int s, int e){
p2(s,e)
pp(siz[curr-1])
p(now)
if(now+1>siz[curr-1].F)return;
res[s] = siz[curr-1].S;
now++;
p2(s,now)
for(auto x : adj[s])
if(x!=e && res[x]==0){
color(x,s);
}
}
int lim;
void solve(int s, int e){
for(auto x : adj[s])
if(x!=e && cnt[x]>=siz[curr-1].F && res[x]==0){
solve(x,s);
if(curr==lim)return;
}
if(cnt[s] >= siz[curr-1].F){
res[s] = siz[curr-1].S;
now = 1;
for(auto x : adj[s])
if(x!=e)
color(x,s);
curr++;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
siz[0] = {a,1};
siz[1] = {b,2};
siz[2] = {c,3};
sort(siz,siz+3);
//swap(siz[0],siz[1]);
int i;
for(i=0;i<p.size();i++){
int x = p[i],y = q[i];
adj[x].push_back(y);
adj[y].push_back(x);
}
res.assign(n,0);
dfs(0,0);
int start,col,los=MOD;
int j;
for(i=0;i<n;i++){
for(j=0;j<3;j++){
if(cnt[i] < siz[j].F)continue;
int waste = cnt[i] - siz[j].F;
//p2(cnt[i],siz[j].F)
//p2(i,j)
if(waste < los){
los = waste;
start = i;
col = j;
}
}
}
p2(start,col)
set<int> cols;
for(i=1;i<=3;i++)cols.insert(i);
curr = col+1;
p2(los,curr)
now = 0;
p(par[start])
pp(siz[curr-1])
color(start,par[start]);
cols.erase(curr);
pv(cols)
pv(res)
curr = *cols.begin();
int need = siz[curr-1].F;
p2(curr,need)
if(res[0] || need > n - cnt[start]){
for(auto &x : res)
x = 0;
return res;
}
now = 0;
color(0,0);
cols.erase(curr);
pv(res)
curr = *cols.begin();
for(auto &x : res)
if(x==0)x = siz[curr-1].S;
return res;
}
/*
11 10
3 4 4
0 1
1 3
1 4
1 5
4 6
0 2
2 7
2 8
7 9
9 10
g++ grader.cpp split3.cpp -Ddremix
*/
