#include <bits/stdc++.h>
#include "split.h"
#define ll long long
#define ld long double
#define pb push_back
#define x first
#define y second
using namespace std;
int n,m;
vector<vector<int>> g(100000);
int a[3],b[3];
vector<int> sz(100000),ans;
bool done=0;
int cnt=0;
set<int> st={0,1,2};
bool vis[100000];
void dfs1(int u, int par)
{
sz[u]=1;
for(int v:g[u])
{
if(v==par) continue;
dfs1(v,u);
sz[u]+=sz[v];
}
}
void dfs3(int u, int par, int val)
{
vis[u]=1;
cnt++;
ans[u]=val;
for(int v:g[u])
{
if(v==par || vis[v]) continue;
if(cnt>=a[val]) break;
dfs3(v,u,val);
}
}
void dfs2(int u, int par)
{
if(done) return;
if(par!=-1) sz[par]-=sz[u];
sz[u]=n;
int found=-1, which=-1, which2=-1;
for(int v:g[u])
{
if(sz[v]>=a[0])
{
if(n-sz[v]>=a[1])
{
found=v;
which=0;
which2=1;
break;
}
if(n-sz[v]>=a[2])
{
found=v;
which=0;
which2=2;
break;
}
}
if(sz[v]>=a[1])
{
if(n-sz[v]>=a[2])
{
found=v;
which=1;
which2=2;
break;
}
if(n-sz[v]>=a[0])
{
found=v;
which=1;
which2=0;
break;
}
}
if(sz[v]>=a[2])
{
if(n-sz[v]>=a[1])
{
found=v;
which=2;
which2=1;
break;
}
if(n-sz[v]>=a[0])
{
found=v;
which=2;
which2=0;
break;
}
}
if(v!=par) dfs2(v,u);
}
if(found>=0)
{
done=1;
st.erase(which);
st.erase(which2);
dfs3(found,u,which);
cnt=0;
dfs3(u,found,which2);
}
sz[u]=n-sz[par];
sz[par]=n;
}
vector<int> find_split(int N, int d, int b, int c, vector<int> p, vector<int> q)
{
n=N;
m=p.size();
a[0]=d, a[1]=b, a[2]=c;
for(int i=0;i<n;i++) ans.pb(-1);
for(int i=0;i<m;i++)
{
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
if(a[0]==1)
{
dfs3(0,0,1);
int to=0;
for(int i=0;i<n;i++) if(ans[i]==-1){ans[i]=to;if(to==0)to=2;}
for(int i=0;i<n;i++) ans[i]++;
}
else{dfs1(0,-1);
dfs2(0,-1);
if(done)
for(int i=0;i<n;i++) if(ans[i]==-1) ans[i]=*st.begin();
for(int i=0;i<n;i++) ans[i]++;}
return ans;
}
