//
#ifndef __SIZEOF_INT128__
#define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
string name{""};
time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
duration<float, std::milli> dur;
Timer() = default;
Timer(string nm): name(nm) {}
~Timer() {
end = high_resolution_clock::now(); dur= end - start;
cout << "@" << name << "> " << dur.count() << " ms" << '\n';
}
};
template <typename T = int> inline T in()
{
static T x;
std::cin >> x;
return x;
}
std::string yn(bool b)
{
if(b) return "YES\n";
else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
for(const auto& i : wek)out << i << ' ';
return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
out << '{'<<par.first<<", "<<par.second<<"}";
return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
constexpr int maxn = 1e5 + 3;
vector <int> graf[maxn];
int low[maxn], siz[maxn], pok[maxn];
vector <int> u[maxn], sy[maxn];
int dfs(int w, int l, int r, int p = 1)
{
low[w] = pok[w] = p;
siz[w] = 1;
int s(1);
vector <pair <int, int>> v;
for(auto i: graf[w]){
if(!pok[i]){
sy[w].pb(i);
int d(dfs(i, l, r, p+1));
if(d)return d;
low[w] = min(low[w], low[i]);
siz[w] += siz[i];
if(low[i] >= p){
s += siz[i];
u[w].pb(i);
}
else if(siz[i] < l)v.pb(i, siz[i]);
}
else if(pok[i] != pok[w]-1)low[w] = min(low[w], pok[i]);
}
// cerr << w << ": " << v << '\n';
int i(0);
while(s < l && i < sz(v)){
u[w].pb(v[i].first);
s += v[i++].second;
}
if(l <= s && s <= r)return w+1;
return 0;
}
bool wpo[maxn];
void dfs2(int w){
wpo[w] = 1;
for(auto i: sy[w])dfs2(i);
}
vector <int> odp;
int dfs3(int w, bool b, int f, int k)
{
// cerr << '(' << w << ' ' << b << ' ' << f << ' ' << k << ")\n";
odp[w] = f;
--k;
for(auto i: graf[w])if(k && !odp[i] && wpo[i] == b)k = dfs3(i, b, f, k);
return k;
}
vector <int> find_split(const int n, int aa, int bb, int cc, vector <int> p, vector <int> q)
{
const int m(sz(p));
int a(min({aa, bb, cc})), c(max({aa, bb, cc})), b(n-a-c);
int ia(aa < bb ? (aa < cc ? 1 : 3) : (bb < cc ? 2 : 3)), ic(aa < bb ? (bb < cc ? 3 : 2) : (aa < cc ? 3 : 1)), ib(6 - ia - ic);
rep(i, 0, m){
graf[p[i]].pb(q[i]);
graf[q[i]].pb(p[i]);
}
int d(dfs(0, a, n-b));
bool ca(0);
if(d == 0){
ca = 1;
rep(i, 0, n){
low[i] = pok[i] = siz[i] = 0;
u[i].clear();
sy[i].clear();
}
d = dfs(0, b, n-a);
if(d == 0)return vector <int>(n, 0);
}
--d;
odp = vector <int>(n, 0);
wpo[d] = 1;
for(auto i: u[d])dfs2(i);
// cerr << d << '\n';
// rep(i, 0, n)cerr << i << ": " << siz[i] << ' ' << pok[i] << ' ' << low[i] << " {" << sy[i] << "} {" << u[i] << "} " << wpo[i] << '\n';
int e(-1);
rep(i, 0, n)if(!wpo[i]){
e = i;
break;
}
if(ca){
swap(d, e);
rep(i, 0, n)wpo[i] = !wpo[i];
}
dfs3(d, 1, ia, a);
dfs3(e, 0, ib, b);
rep(i, 0, n)if(!odp[i])odp[i] = ic;
return odp;
}
