#include <bits/stdc++.h>
#include "split.h"
#define f first
#define s second
#define ent '\n'
//#define int long long
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
//typedef long double ld;
typedef long long ll;
using namespace std;
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}
struct seg{
int m1,m2,sum,cnt;
};
const string out[2]={"No\n","Yes\n"};
const ll dx[]={0,0,1,-1,-1,1,1,-1};
const ll dy[]={1,-1,0,0,-1,1,-1,1};
const int md=998244353;
const int mod=1e9+7;
const int mx=1e6+1;
const int tst=1e5;
const bool T=0;
vector<pair<int,int>> orz;
vector<int> g[mx];
vector<int> ord;
bool used[mx];
int tin[mx];
int fup[mx];
int ans[mx];
int sz[mx];
int n,m,k;
int A,B,C;
int timer;
int cnt;
int ver;
bool ok;
void dfs(int v){
used[v]=1;
cnt++;
if(cnt<=A){
ans[v]=1;
}
else if(cnt<=A+B){
ans[v]=2;
}
else{
ans[v]=3;
}
for(int to:g[v]){
if(!used[to]){
dfs(to);
}
}
}
void dfs(int v,int p){
used[v]=sz[v]=1;
tin[v]=fup[v]=++timer;
int mn=1e9,c=0;
for(int to:g[v]){
if(!used[to]){
dfs(to,v);
fup[v]=min(fup[v],fup[to]);
mn=min(mn,fup[to]);
sz[v]+=sz[to];
c++;
}
if(used[to] && to!=p){
fup[v]=min(fup[v],tin[to]);
}
}
if(mn>=tin[v] && p && mn!=1e9){
ord.push_back(v);
}
if(!p && c>1){
ord.push_back(v);
}
}
void dfst(int v,int p=0){
sz[v]=1;
for(int to:g[v]){
if(to!=p){
dfst(to,v);
sz[v]+=sz[to];
}
}
if(sz[v]>=A && n-sz[v]>=B){
ver=v;
ok=0;
}
if(sz[v]>=B && n-sz[v]>=A){
ver=v;
ok=1;
}
}
void ddd(int v){
used[v]=1;
for(int to:g[v]){
if(!used[to]){
ddd(to);
orz.push_back({v,to});
}
}
}
void dfs2(int v,bool f){
cnt++;
used[v]=1;
if(cnt<=A && !f){
ans[v]=1;
}
if(cnt<=B && f){
ans[v]=2;
}
random_shuffle(g[v].begin(),g[v].end());
for(int to:g[v]){
if(!used[to]){
dfs2(to,f);
}
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q){
n=N;
srand(time(0));
m=p.size();
A=a,B=b,C=c;
int mn=1e9,pos=0;
bool okk=1;
for(int i=0;i<p.size();i++){
p[i]++;
q[i]++;
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
for(int i=1;i<=n;i++){
if(g[i].size()>2){
okk=0;
}
mn=min(mn,(int)g[i].size());
if(mn==(int)g[i].size()){
pos=i;
}
}
if(okk){
dfs(1);
vector<int> v;
for(int i=1;i<=n;i++){
v.push_back(ans[i]);
}
return v;
}
if(a==1){
dfs(1,0);
for(int i=1;i<=n;i++){
used[i]=0;
}
for(int x:ord){
used[x]=1;
}
int u=1;
while(used[u]){
u++;
}
vector<int> v;
ans[u]=1;
for(int i=1;i<=n;i++){
used[i]=0;
}
used[u]=1;
cnt=1;
if(u!=1)dfs(1);
else dfs(2);
for(int i=1;i<=n;i++){
v.push_back(ans[i]);
}
return v;
}
ddd(1);
for(int i=1;i<=n;i++){
g[i].clear();
}
for(auto x:orz){
g[x.f].push_back(x.s);
g[x.s].push_back(x.f);
}
for(int i=1;i<=n;i++){
used[i]=0;
}
dfst(1);
if(!ver){
vector<int> v;
for(int i=1;i<=n;i++){
v.push_back(0);
}
return v;
}
if(ok){
used[ver]=1;
cnt=0;
dfs2(1,0);
cnt=0;
dfs2(ver,1);
}
else{
used[ver]=1;
cnt=0;
dfs2(1,1);
cnt=0;
dfs2(ver,0);
}
vector<int> v;
for(int i=1;i<=n;i++){
if(!ans[i]){
ans[i]=3;
}
v.push_back(ans[i]);
}
return v;
}
