#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5;
vector<int> nei[M], cc;
int subt[M], dep[M], mnd[M];
bool vis[M];
void init(int u)
{
subt[u]=1, vis[u]=1;
mnd[u]=dep[u];
for (int i:nei[u])
if (!vis[i])
dep[i]=dep[u]+1, init(i), mnd[u]=min(mnd[u],mnd[i]), subt[u]+=subt[i];
else
mnd[u]=min(mnd[u],dep[i]);
}
void dfs(int u, int a)
{
cc.push_back(u);
vis[u]=1;
for (int i:nei[u])
{
if (cc.size()==a) break;
if(!vis[i])
dfs(i,a);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
int m=p.size();
for (int i=0;i<m;i++)
nei[p[i]].push_back(q[i]), nei[q[i]].push_back(p[i]);
init(0);
vector<int> ans(n);
vector<pair<int,int>> ord={{a,1},{b,2},{c,3}};
sort(ord.begin(),ord.end());
a=ord[0].first, b=ord[1].first;
int u;
for (int i=0;i<n;i++)
{
bool b=(subt[i]>=a);
for (int v:nei[i])
if (dep[v]==dep[i]+1)
b&=(subt[v]<a);
if (b) u=i;
}
int x=n-subt[u];
for (int i=0;i<n;i++)
if (dep[i]>=dep[u]) vis[i]=0;
for (int i:nei[u])
{
if (x>=a) break;
if (dep[i]==dep[u]+1 && mnd[i]<dep[u])
x+=subt[i], subt[u]-=subt[i], vis[i]=1;
}
if (x<a) return ans;
dfs(u,a);
for (int i:cc) ans[i]=ord[0].second;
cc.clear();
for (int i:nei[u]) if(dep[i]>dep[u]) vis[i]=1;
dfs(0,b);
for (int i:cc) ans[i]=ord[1].second;
for (int i=0;i<n;i++)
if (!ans[i]) ans[i]=ord[2].second;
return ans;
}
