#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=200007;
bool odw[N];
int s[N];
vector<int>G[N];
set<int>G1[N];
vector<pair<int,int>>E;
vector<int>ans;
void dfs(int v)
{
odw[v]=1;
s[v]=1;
for(auto u:G[v])
{
if(!odw[u])
{
G1[v].insert(u);
G1[u].insert(v);
dfs(u);
s[v]+=s[u];
}
else E.pb({u,v});
}
}
int C;
void get(int v,int o,int k)
{
if(C==0) return;
ans[v]=k;
C--;
for(auto u:G1[v])
{
if(u==o) continue;
get(u,v,k);
}
}
vector<int> find_split(int n,int a,int b,int c,vector<int>P,vector<int>Q)
{
vector<pair<int,int>>V;
V.pb({a,1});
V.pb({b,2});
V.pb({c,3});
sort(all(V));
int A=V[0].st,B=V[1].st;
for(int i=0;i<sz(P);i++)
{
G[P[i]].pb(Q[i]);
G[Q[i]].pb(P[i]);
}
dfs(0);
ans.resize(n,0);
int v=0;
bool is=0;
while(v!=-1)
{
int mx=0,p=-1;
for(auto u:G1[v])
{
if(s[u]<s[v]&&s[u]>mx)
{
mx=s[u];
p=u;
}
}
if(mx<A) break;
if(mx>=A&&n-mx>=B)
{
for(int i=0;i<n;i++) ans[i]=V[2].nd;
C=A;
get(p,v,V[0].nd);
C=B;
get(v,p,V[1].nd);
is=1;
break;
}
if(mx>=B&&n-mx>=A)
{
for(int i=0;i<n;i++) ans[i]=V[2].nd;
C=B;
get(p,v,V[1].nd);
C=A;
get(v,p,V[0].nd);
is=1;
break;
}
v=p;
}
return ans;
}
/*
int main()
{
vector<int>V=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
for(auto x:V) cout<<x<<" ";
cout<<endl;
return 0;
}
*/
