#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define fr first
#define er erase
#define in insert
#define sc second
#define ll long long
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define len(x) (ll) x.size()
#define all(x) x.begin(),x.end()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll maxn = 1e5 + 5;
ll n, m, k = 0;
#include "split.h"
mt19937 rng(clock());
vll g[maxn];
ll sz[maxn];
void dfs(ll u, ll p = -1){
sz[u] ++;
for(auto v : g[u]){
if(v == p) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
vll ve;
void dfs2(ll u, ll rest, ll p = -1){
// ve.pb(u);
if(len(ve) >= k) return;
for(auto v : g[u]){
if(v == rest or v == p) continue;
dfs2(v, rest, u);
if(len(ve) >= k) return;
}
}
pair<vll, vll>f(ll a, ll b){
if(a > b) swap(a, b);
// 7 balliq subtask : cycle (AC)
// 11 balliq subtask : a = 1 (AC)
// 22 balliq subtask : tree
// birde burdan sonra artiq alinmayan hallar var
// eger treedise, demeli ele node tapa bilerik ki, ordan rootlayanda, ele bir v subtreesi olsun ki, len(v) >= a olsun,
// ve n - len(v) >= b olsun.
// onda bize bele v-lerden elesi lazimdi ki, minimum olsun. v-nin subtreelerinin hec biri ucun size >= a olmasin.
// aglima yol gelmir birinci random ile kecirmeyi yoxluyacam
set<ll>s;
auto get = [&]() -> ll{
if(len(s) == n) return n + 1;
ll x = rng() % n;
while(s.find(x) != s.end()) x = rng() % n;
s.in(x);
return x;
};
vll ax, bx;
for(ll tt = 0; tt <= 500; tt ++){
ll r = get();
if(r > n) break;
for(ll i = 0; i < n; i ++) sz[i] = 0;
dfs(r);
ll f = 0;
for(auto ch : g[r]){
if(sz[ch] >= a and n - sz[ch] >= b){
f = ch;
break;
}
}
if(f){
k = a;
ve.clear();
dfs2(f, r);
ax = ve;
k = b;
ve.clear();
dfs2(r, f);
bx = ve;
break;
}
}
return {ax, bx};
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n;
for(ll i = 0; i < len(p); i ++){
g[p[i]].pb(q[i]), g[q[i]].pb(p[i]);
}
vector<int>cv(n);
if(_a <= _c and _b <= _c){
auto [ax, bx] = f(_a, _b);
if(_a > _b) swap(ax, bx);
if(len(ax) != _a) return cv;
cv.assign(n, 3);
for(auto i : ax) cv[i] = 1;
for(auto i : bx) cv[i] = 2;
}
else if(_a <= _b and _c <= _b){
auto [ax, cx] = f(_a, _c);
if(_a > _c) swap(ax, cx);
if(len(ax) != _a) return cv;
cv.assign(n, 2);
for(auto i : ax) cv[i] = 1;
for(auto i : cx) cv[i] = 3;
}
else{
auto [bx, cx] = f(_b, _c);
if(_b > _c) swap(bx, cx);
if(len(bx) != _b) return cv;
cv.assign(n, 1);
for(auto i : bx) cv[i] = 2;
for(auto i : cx) cv[i] = 3;
}
return cv;
}
// void _() {
// }
// signed main() {
// ll tm = clock();
// cin.tie(0)->sync_with_stdio(0);
// ll t = 1;
// // cin >> t;
// for(ll tt = 1; tt <= t; tt ++) _();
// cerr << "\n\033[1;31mTime: \033[1;30m" \
// << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n";
// }
