#include <bits/stdc++.h>
#include <split.h>
#define fu(_i,_a,_b) for (int _i=_a; _i<=_b; _i++)
#define fd(_i,_a,_b) for (int _i=_a; _i>=_b; _i--)
#define pb push_back
#define ALL(VecS) VecS.begin(),VecS.end()
#define x first
#define y second
#define task "split"
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ll> il;
typedef pair<ll,int> li;
typedef vector <int> vi;
const int N=100005;
const ll BASE=10000;
int n, m, a, par[N], depth[N], s[N], R=1, mrk[N], b, cnt, c1, ans[N], ca, cb;
ii A[4];
vi G[N];
void dfs(int u)
{
s[u]=1;
for (int v: G[u])
if (!depth[v])
{
depth[v]=depth[u]+1;
//cout << u << " " << v << '\n';
dfs(v);
s[u]+=s[v];
}
}
void DFS(int u)
{
for (int v: G[u])
if (depth[v]==depth[u]+1)
{
if (s[v]>=a)
{
if (depth[v]>depth[R]) R=v;
DFS(v);
}
}
}
void DFS1(int u)
{
par[u]=1;
for (int v: G[u])
if (depth[v]==depth[u]+1)
{
DFS1(v);
for (int k: G[v])
if (par[k]==0) {mrk[v]=1; break;}
}
}
void Mk(int u)
{
par[u]=0;
s[R]--;
b++;
for (int v: G[u])
if (depth[v]==depth[u]+1)
Mk(v);
}
void Hsgi(int u)
{
//cout << u << ' ';
if (b>=a) return;
if (mrk[u]==1 && s[R]-s[u]>=a) {Mk(u); return;}
for (int v: G[u])
if (depth[v]==depth[u]+1) Hsgi(v);
}
void pra(int u,int clr, int z)
{
if (ca==0) return;
if (par[u]==clr) ans[u]=z;
ca--;
for (int v: G[u])
if (depth[v]==depth[u]+1)
{
if (par[v]==clr) pra(v,clr,z);
}
}
vi find_split(int n, int AA, int BB, int CC, vi p, vi q)
{
fu(i,1,n) par[i]=0;
A[1].x=AA; A[2].x=BB; A[3].x=CC;
A[1].y=1; A[2].y=2; A[3].y=3;
sort(A+1,A+4);
a=min({A[1].x,A[2].x,A[3].x});
int u,v;
m=p.size();
fu(i,1,m)
{
u=p[i-1]+1,v=q[i-1]+1;
u++; v++;
G[u].pb(v);
G[v].pb(u);
}
depth[1]=1;
depth[0]=0;
dfs(1);
DFS(1);
DFS1(R);
b=n-s[R];
Hsgi(R);
if (b<a) fu(i,1,n) ans[i]=0;
else
{
if (b>=A[2].x) {ca=A[2].x; pra(1,0,A[2].y); ca=A[1].x; pra(R,1,A[1].y);}
else { ca=A[2].x; pra(R,1,A[2].y); ca=A[1].x; pra(1,0,A[1].y);}
fu(i,1,n) if (!ans[i]) ans[i]=A[3].y;
//fu(i,1,n) cout << ans[i] << " ";
}
vi Ans;
fu(i,1,n) Ans.pb(ans[i]);
return Ans;
}
/*int main()
{
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
//cin >> n >> m;
fu(i,1,n) par[i]=0;
cin >> A[1].x >> A[2].x >> A[3].x;
A[1].y=1; A[2].y=2; A[3].y=3;
sort(A+1,A+4);
a=min({A[1].x,A[2].x,A[3].x});
int u,v;
fu(i,1,m)
{
cin >> u >> v;
u++; v++;
G[u].pb(v);
G[v].pb(u);
}
depth[1]=1;
depth[0]=0;
dfs(1);
DFS(1);
DFS1(R);
b=n-s[R];
Hsgi(R);
if (b<a) fu(i,1,n) cout << "0" << ' ';
else
{
if (b>=A[2].x) {ca=A[2].x; pra(1,0,A[2].y); ca=A[1].x; pra(R,1,A[1].y);}
else { ca=A[2].x; pra(R,1,A[2].y); ca=A[1].x; pra(1,0,A[1].y);}
fu(i,1,n) if (!ans[i]) ans[i]=A[3].y;
fu(i,1,n) cout << ans[i] << " ";
}
return 0;
}*/
