#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int len = 1e5+5;
vector<int> adj[len], out;
int vis[len], n, sz1, sz2, sz3, col1, col2, col3;
void paint(int u, int p, int &rem, int col){
//printf("painting: u = %d, p = %d, rem = %d, col = %d\n", u, p, rem, col);
vis[u] = col, rem--;
if (rem == 0) return;
for (auto v: adj[u]){
if (v == p || vis[v]) continue;
paint(v, u, rem, col);
if (rem == 0) return;
}
}
struct{
int sz[len];
int fix(int u, int p, int &yes){
//printf("fix: u = %d, p = %d\n", u, p);
int ans = 1;
for (auto v: adj[u]){
if (v == p) continue;
int sz = fix(v, u, yes);
if (yes) return 0;
ans += sz;
if (sz1 <= sz && sz2 <= n-sz){
paint(v, u, sz1, col1);
paint(u, v, sz2, col2);
return (yes = 1);
}
if (sz1 <= n-sz && sz2 <= sz){
paint(u, v, sz1, col1);
paint(v, u, sz2, col2);
return (yes = 1);
}
}
return ans;
}
void solve(){
int yes = 0;
fix(1, 1, yes);
if (!yes) return;
for (int i = 1; i <= n; i++){
if (!vis[i]) vis[i] = col3;
out[i-1] = vis[i];
}
}
} sub3;
struct{
void solve(){
int st = 1;
for (int i = 1; i <= n; i++)
if (adj[i].size() == 1)
st = i;
paint(st, st, sz2, col2);
for (int i = 1; i <= n; i++)
if (!vis[i]){
paint(i, i, sz1, col1);
break;
}
for (int i = 1; i <= n; i++){
if (!vis[i])
vis[i] = col3;
out[i-1] = vis[i];
}
}
} sub12;
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);
//printf("sz1 = %d, sz2 = %d, sz3 = %d\n", sz1, sz2, sz3);
//printf("col1 = %d, col2 = %d, col3 = %d\n", col1, col2, col3);
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);
}
out.resize(n, 0);
if (P.size() == n-1)
sub3.solve();
else
sub12.solve();
return out;
}
