#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;
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 = 0){
//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);
ans += sz;
if (sz1 <= sz && sz2 <= n-sz){
paint(v, u, sz1, 1);
paint(u, v, sz2, 2);
return 0;
}
if (sz1 <= n-sz && sz2 <= sz){
paint(u, v, sz1, 1);
paint(v, u, sz2, 2);
return 0;
}
}
return ans;
}
void solve(){
fix(1);
int yes = 0;
for (int i = 1; i <= n; i++)
if (vis[i]) yes = 1;
if (!yes) return;
for (int i = 1; i <= n; i++){
if (!vis[i]) vis[i] = 3;
out.pb(vis[i]);
}
}
} sub3;
struct{
void solve(){
for (int i = 1; i <= n; i++)
if (!vis[i]){
paint(i, i, sz2, 2);
break;
}
for (int i = 1; i <= n; i++)
if (!vis[i]){
paint(i, i, sz1, 1);
break;
}
for (int i = 1; i <= n; i++){
if (!vis[i])
vis[i] = 3;
out.pb(vis[i]);
}
}
} sub12;
vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
n = N;
if (B < A) swap(A, B);
if (C < A) swap(A, C);
if (C < B) swap(B, C);
sz1 = A, sz2 = B, sz3 = C;
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;
}
