#include <bits/stdc++.h>
#include "split.h"
// #include "grader.cpp" // rem
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for (int i = (n); i >= 1; i--)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const ll maxn = 1e5+5;
const ll inf = 1e9;
const ll mod = 998244353;
ll pw(ll x, ll p, ll m){
ll ret = 1;
while(p > 0){
if (p & 1){
ret *= x;
ret %= m;
}
x *= x;
x %= m;
p >>= 1;
}
return ret;
}
ll inv(ll x, ll m){
return pw(x, m-2, m);
}
int n, a, b, c; // a, b, c sorted in this case
vector<int> g[maxn];
vector<int> sz(maxn), low(maxn), occ(maxn), dep(maxn);
bool dfsocc = 0;
vector<int> S1, S2;
vector<bool> s1occ(maxn), s2occ(maxn);
void dfs2(int x, int prev){
S1.pb(x);
s1occ[x] = 1;
for (auto y:g[x]){
if (dep[y] == dep[x]+1){
dfs2(y, x);
}
}
}
void dfs3(int x, int prev){
S2.pb(x);
s2occ[x] = 1;
for (auto y:g[x]){
if (dep[y] == dep[x]+1){
dfs3(y, x);
}
}
}
void dfs4(int x){ // so that prefixes can be connected in S1
s1occ[x] = 1;
S1.pb(x);
for (auto y:g[x]){
if (s1occ[y] || s2occ[y]) continue;
dfs4(y);
}
}
void dfs1(int x, int prev){
occ[x] = 1;
sz[x] = 1;
low[x] = dep[x];
for (auto y:g[x]){
if (y == prev) continue;
if (occ[y]){
low[x] = min(low[x], low[y]);
}
else{
dep[y] = dep[x]+1;
dfs1(y, x);
low[x] = min(low[x], low[y]);
sz[x] += sz[y];
}
}
if (sz[x] >= a && !dfsocc){
dfsocc = 1;
dfs2(x, prev); // get all the s1occ
S1.clear();
REP(i, n){
s1occ[i] = (s1occ[i]^1);
if (s1occ[i]) S1.pb(i);
}
int ta, tb;
for (auto y:g[x]){
if (SZ(S1) >= a) break;
if (dep[y] == dep[x]+1 && low[y] < dep[x]){
dfs2(y, x);
}
}
ta = SZ(S1);
S2.pb(x);
s2occ[x] = 1;
for (auto y:g[x]){
if (dep[y] == dep[x]+1 && !s1occ[y]){
dfs3(y, x);
}
}
if (SZ(S1)){
int u = S1[0]; S1.clear();
fill(ALL(s1occ), 0);
dfs4(u);
}
tb = SZ(S1);
return;
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
n = N;
dfsocc = 0;
vector<pii> pus = {{A, 0}, {B, 1}, {C, 2}};
REP(i, SZ(p)){
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
sort(ALL(pus)); // by smallest
a = pus[0].f, b = pus[1].f;
dfs1(0, -1);
vector<int> ret;
REP(i, n) ret.pb(-1);
//assert(SZ(S1) + SZ(S2) == n);
if (SZ(S1) > SZ(S2)) swap(S1, S2);
if (SZ(S1) < a){
fill(ALL(ret), 0);
return ret;
}
// match S1 with a, S2 with b
REP(i, a) ret[S1[i]] = 0;
REP(i, b) ret[S2[i]] = 1;
REP(i, n) if (ret[i] == -1) ret[i] = 2;
REP(i, n) ret[i] = pus[ret[i]].s + 1; // convert it back
return ret;
}
/*
9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
5 6
2 2 1
0 2
0 1
1 2
1 3
2 3
3 4
*/
