#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;
vll g[maxn];
ll a, b, c, vis[maxn];
// verilen qraf SCC-di
// ve men {a, b, c} = sort({a, b, c}) kimi goturmusem
// biz bu SCC-ni bir dene node-dan rootlayanda cavabin alinmasi ucun gerek child SCC-lerden biri:
// ya a size-li SCC duzeltmek olsun ve n - a > b olsun
// ya da b size-li SCC duzeltmek olsun ve n - b > a olsun
// n - a > b ve n - b > a hemise duzdu
// onda ele a size-li SCC duzeltmek olan child SCC-den duzeldek, b size-li SCC-ni ise adi bfs ile duzeldek
// ez
ll dfs(ll u, ll le, ll co){
vis[u] = co;
if(le == a) return 1;
for(auto v : g[u]){
if(vis[v]) continue;
if(dfs(v, le + 1, co)) return 1;
}
return 0;
}
vector<int>cv;
void dfs2(ll u){
vis[u] = n + 1;
cv[u - 1] = 2;
b --;
if(b == 0) return;
for(auto v : g[u]){
if(vis[v] != n + 1) dfs2(v);
}
}
ll cal[4], in[maxn];
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
n = _n, a = _a, b = _b, c = _c;
cal[1] = 1, cal[2] = 2, cal[3] = 3;
cv.assign(n, 3);
if(a > b) swap(a, b), swap(cal[1], cal[2]);
if(a > c) swap(a, c), swap(cal[1], cal[3]);
if(b > c) swap(b, c), swap(cal[2], cal[3]);
for(ll i = 0; i < len(p); i ++){
g[p[i] + 1].pb(q[i] + 1);
g[q[i] + 1].pb(p[i] + 1);
in[q[i] + 1] ++, in[p[i] + 1] ++;
}
ll best = 0, bestv = 0;
for(ll i = 1; i <= n; i ++){
if(in[i] > bestv){
best = i;
bestv = in[i];
}
}
ll ch = 0;
for(auto v : g[bestv]){
if(vis[v]) continue;
if(dfs(v, 1, v)){
for(ll i = 1; i <= n; i ++){
if(vis[i] == v) cv[i - 1] = 1;
}
ch = v;
break;
}
}
if(!ch){
for(ll i = 0; i <= n - 1; i ++) cv[i] = 0;
return cv;
}
for(auto v : g[1]){
if(vis[v] == ch) continue;
dfs2(v);
if(b == 0) break;
}
for(ll i = 0; i <= n - 1; i ++){
cv[i] = cal[cv[i]];
}
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";
// }
