#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
int n,m,sz[MAXN],depth[MAXN],par[MAXN],mindepth[MAXN],val[MAXN],vis[MAXN];
bool vis2[MAXN];
pair<int,int> a[5];
vector<int> adj[MAXN],rs;
int dfs2(int u, int x, int k){
if(k==0) return 0;
val[u]=x, --k;
for(int& v : adj[u])
if(vis[v]==2&&!vis2[v]&&val[v]==0) k=dfs2(v,x,k);
return k;
}
int dfs3(int u, int x, int k){
if(k==0) return 0;
val[u]=x, --k;
for(int& v : adj[u])
if(val[v]==0) k=dfs3(v,x,k);
return k;
}
bool dfs(int u){
if(!rs.empty()) return 1;
vector<int> child;
bool ok=0;
sz[u]=vis[u]=1;
mindepth[u]=depth[u];
for(int& v : adj[u]){
if(!vis[v]){
par[v]=u, depth[v]=depth[u]+1, ok|=dfs(v), sz[u]+=sz[v];
if(mindepth[v]<depth[u]) child.pb(v);
mindepth[u]=min(mindepth[u],mindepth[v]);
}
else mindepth[u]=min(mindepth[u],depth[v]);
}
vis[u]=2;
if(!ok&&sz[u]>=a[1].fi){
vector<int> tmp;
int SZ=sz[u];
while(n-SZ<a[1].fi&&!child.empty()) SZ-=sz[child.back()], tmp.pb(child.back()), vis2[child.back()]=1, child.pob();
if(n-SZ>=a[1].fi){
if(SZ>=a[2].fi){
dfs2(u,a[2].se,a[2].fi);
dfs3(1,a[1].se,a[1].fi);
}else{
dfs2(u,a[1].se,a[1].fi);
dfs3(1,a[2].se,a[2].fi);
}
for(int i = 1; i<=n; ++i){
if(val[i]==0) rs.pb(a[3].se);
else rs.pb(val[i]);
}
}
while(!tmp.empty()) vis2[tmp.back()]=0, tmp.pob();
return 1;
}
return ok;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q){
n=N, m=sz(p);
a[1].fi=A, a[2].fi=B, a[3].fi=C;
for(int i = 1; i<=3; ++i)
a[i].se=i;
sort(a+1,a+4);
for(int i = 0; i<m; ++i){
int x=p[i], y=q[i];
++x, ++y;
adj[x].pb(y), adj[y].pb(x);
}
dfs(1);
if(rs.empty()){
for(int i = 1; i<=n; ++i)
rs.pb(0);
}
return rs;
}
