#include "split.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//#define int ll
#define ve vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fv(a, c) for(int (a) = (1); (a) <= (c); (a)++)
#define fz(a, c) for(int (a) = (0); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define pb push_back
#define in insert
#define ss second
#define ff first
#define vi vector <int>
#define fa(a, v) for(auto (a) : (v))
#define mnel(a) *min_element(all(a))
#define mxel(a) *max_element(all(a))
#define si set<int>
#define sov(a) sort(all((a)))
ve<vi> G, C;
vi num, siz, low;
int n, x;
pii X, Y, Z;
bool found = 0, sol = 0;
tuple<int, int, int> top ,bottom;
vector <bool> B;
void dfs (int u, int p){
siz[u] = 1;
x ++;
num[u] = x;
low[u] = x;
bool ok = 1;
fa(v, G[u]){
if(num[v] == 0){
dfs(v, u);
siz[u] += siz[v];
low[u] = min(low[v], low[u]);
if(siz[v] >= X.ff)
ok = 0;
C[u].pb(v);
}
else
if(v != p)
low[u] = min(low[u], num[v]);
}
if(siz[u] < X.ff)
ok = 0;
if(ok && !found){
// cout << "found: " << u << " " << p << "\n";
found = 1;
int cur = siz[u];
fa(v, C[u]){
if(low[v] < num[u]){
if(cur - siz[v] >= X.ff){
B[v] = 1;
cur -= siz[v];
}
}
}
int opt = n - cur;
if(opt >= Y.ff){
sol = 1;
top = {Y.ff, Y.ss, p};
bottom = {X.ff, X.ss, u};
}
else
if(opt >= X.ff){
sol = 1;
top = {X.ff, X.ss, p};
bottom = {Y.ff, Y.ss, u};
}
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
vi ans(n);
int m = p.size();
n = nn;
G = ve<vi> (n);
C = ve<vi> (n);
num = vi (n);
siz = vi (n);
low = vi (n);
B = ve<bool> (n);
queue <int> Q;
fp(i,0,m){
G[p[i]].pb(q[i]);
G[q[i]].pb(p[i]);
}
ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
sort(all(A));
X = A[0], Y = A[1], Z = A[2];
dfs(0, -1);
fp(i,0,n)
// cout << i << " " << siz[i] << "\n";
if(sol){
ans = vi (n, Z.ss);
int sz, d, s;
tie(sz, d, s) = bottom;
ans[s] = d;
sz --;
Q.push(s);
while(Q.size()){
int u = Q.front();
Q.pop();
fa(v, C[u]){
if(!B[v]){
if(sz > 0){
ans[v] = d;
Q.push(v);
sz --;
}
}
}
}
tie(sz, d, s) = top;
ans[s] = d;
sz--;
Q.push(s);
// cout << "top" << " ";
while(Q.size()){
int u = Q.front();
Q.pop();
fa(v, G[u]){
// cout << v << " " << ans[v] << "\n";
if(ans[v] == Z.ss){
if(sz > 0){
sz--;
ans[v] = d;
Q.push(v);
}
}
}
}
}
else
ans = vi (n, 0);
return ans;
}
