#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define SZ(x) ll((x).size())
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
const int MAXN = 2e5 + 10;
int n , m , A[3] , C[3] , mark[MAXN] , sz[MAXN] , par[MAXN] , col[MAXN] , intree[MAXN];
vector<pii> adj[MAXN];
void DFS(int v){
mark[v] = sz[v] = 1;
for(pii i : adj[v]){
int u = i.X , ind = i.Y;
if(mark[u]) continue;
par[u] = v; intree[ind] = 1;
DFS(u);
sz[v] += sz[u];
}
}
void SolveDFS(int v , int p , int color){
if(A[color] == 0) return;
A[color]--;
col[v] = C[color];
for(pii i : adj[v]){
int u = i.X , ind = i.Y;
if(intree[ind] == 0 || u == p) continue;
SolveDFS(u , v , color);
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N; m = SZ(p); A[0] = a; A[1] = b; A[2] = c;
C[0] = 1; C[1] = 2; C[2] = 3;
for(int i = 0 ; i < 3 ; i++){
for(int j = 0 ; j < 2 ; j++){
if(A[i] > A[i + 1]){
swap(A[i] , A[i + 1]);
swap(C[i] , C[i + 1]);
}
}
}
for(int i = 0 ; i < m ; i++){
int v = p[i] , u = q[i];
adj[v].push_back({u , i});
adj[u].push_back({v , i});
}
int flag = 0;
srand(645674156);
for(int _ = 0 ; _ < 20 ; _++){
memset(mark , 0 , sizeof(mark));
memset(sz , 0 , sizeof(sz));
memset(par , 0 , sizeof(par));
memset(intree , 0 , sizeof(intree));
for(int i = 0 ; i < n ; i++){
random_shuffle(all(adj[i]));
}
int root = rand() % n;
DFS(root);
for(int i = 0 ; i < n ; i++){
if(i == root) continue;
if(A[0] <= sz[i] && sz[i] <= n - A[0]){
if(sz[i] <= n / 2){
SolveDFS(i , par[i] , 0);
SolveDFS(par[i] , i , 1);
}
else{
SolveDFS(par[i] , i , 0);
SolveDFS(i , par[i] , 1);
}
flag = 1;
break;
}
}
if(flag){
break;
}
}
vector<int> res;
for(int i = 0 ; i < n ; i++){
if(flag == 0){
res.push_back(0);
}
else if(col[i]){
res.push_back(col[i]);
}
else{
res.push_back(C[2]);
}
}
return res;
}
