#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int len = 1e5+5;
vector<int> adj[len];
int vis[len], num[len], low[len], par[len], sz[len];
int n, sz1, sz2, sz3, col1, col2, col3, cnt;
void fix(int u){
num[u] = low[u] = ++cnt;
sz[u] = 1;
for (auto v: adj[u]){
if (!num[v]){
par[v] = u;
fix(v);
sz[u] += sz[v];
low[u] = min(low[u], low[v]);
}
else if (v != par[u] && num[v] < num[u])
low[u] = min(low[u], num[v]);
}
}
void add(int u, vector<int> &mys){
mys.pb(u);
for (auto v: adj[u]){
if (par[v] != u) continue;
add(v, mys);
}
}
void dfs(int u, vector<int> &mys){
for (auto v: adj[u]){
if (par[v] != u) continue;
if (sz[v] >= sz1)
return void(dfs(v, mys));
}
mys.pb(u);
vector<int> temp;
for (auto v: adj[u]){
if (par[v] != u) continue;
if (low[v] >= num[u])
add(v, mys);
else
temp.pb(v);
}
while (mys.size() < sz1){
add(temp.back(), mys);
temp.pop_back();
}
return;
}
void paint(int u, int &rem, int col){
//printf("painting: u = %d, rem = %d, col = %d\n", u, rem, col);
vis[u] = col, rem--;
if (rem == 0) return;
for (auto v: adj[u]){
if (vis[v]) continue;
paint(v, rem, col);
if (rem == 0) return;
}
}
void print(vector<int> vec){
for (auto cur: vec)
printf("%d ", cur);
printf("\n");
}
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
n = N;
sz1 = A, sz2 = B, sz3 = C;
col1 = 1, col2 = 2, col3 = 3;
if (sz2 < sz1)
swap(sz2, sz1), swap(col2, col1);
if (sz3 < sz1)
swap(sz3, sz1), swap(col3, col1);
if (sz3 < sz2)
swap(sz3, sz2), swap(col3, col2);
for (int i = 0; i < P.size(); i++){
int a = P[i], b = Q[i];
a++, b++;
adj[a].pb(b);
adj[b].pb(a);
}
fix(1);
vector<int> fir, sec;
dfs(1, fir);
sort(fir.begin(), fir.end());
for (int i = 1, j = 0; i <= n; i++){
while (j < fir.size() && fir[j] < i)
j++;
if (j < fir.size() && fir[j] == i)
continue;
sec.pb(i);
}
if (fir.size() >= sec.size())
swap(fir, sec);
//printf("fir: "), print(fir);
//printf("sec: "), print(sec);
if (fir.size() >= sz1){
for (auto u: sec)
vis[u] = col3;
paint(fir.back(), sz1, col1);
for (int u: fir)
if (!vis[u])
vis[u] = col3;
for (int u: sec)
vis[u] = 0;
paint(sec.back(), sz2, col2);
for (int u: sec)
if (!vis[u])
vis[u] = col3;
}
vector<int> out(n, 0);
for (int i = 1; i <= n; i++)
out[i-1] = vis[i];
return out;
}
