#include "split.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200010;
vector<pii> edge;
vector<int> adj[MAXN];
vector<int> tr[MAXN];
int siz[MAXN];
int vis[MAXN];
int nbcc;
vector<int> bcc[MAXN];
int d[MAXN];
int lo[MAXN];
void link_tr(int a, int b) {
edge.eb(a, b);
tr[a].eb(b);
tr[b].eb(a);
}
vector<int> st;
void dfs_ap(int n, int dep) {
d[n] = lo[n] = dep;
st.eb(n);
for(auto &i:adj[n]) {
if(d[i]) {
lo[n] = min(lo[n], d[i]);
} else {
dfs_ap(i, dep + 1);
lo[n] = min(lo[n], lo[i]);
// bcc found
if(lo[i] >= d[n]) {
while(st.back() != n) {
bcc[nbcc].eb(st.back());
st.pop_back();
}
bcc[nbcc].eb(n);
nbcc++;
}
}
}
}
int dfs_siz(int n, int p, int N) {
siz[n] = (n < N);
for(auto &i:tr[n]) if(i != p) {
siz[n] += dfs_siz(i, n, N);
}
return siz[n];
}
vector<int> comp(int n, int ban, int cnt, int N) {
memset(vis, 0, sizeof(vis));
vis[ban] = 1; vis[n] = 1;
queue<int> que;
que.emplace(n);
vector<int> res;
while(!que.empty()) {
int cur = que.front(); que.pop();
if(cur < N) {
res.eb(cur);
cnt--;
if(cnt == 0) return res;
}
for(auto &i:tr[cur]) if(!vis[i]) {
vis[i] = 1;
que.emplace(i);
}
}
assert(false);
return res;
}
vector<int32_t> find_split(int32_t n, int32_t a, int32_t b, int32_t c, vector<int32_t> p, vector<int32_t> q) {
int x, y;
{
vector<int> ord = {a, b, c};
sort(all(ord));
x = ord[0]; y = ord[1];
}
auto get_id = [&](int k) {
if(k == a) return 1;
if(k == b) return 2;
return 3;
};
int m = sz(p);
// assert(m == n - 1);
For(i, 0, m - 1) {
int s = p[i];
int t = q[i];
adj[s].eb(t);
adj[t].eb(s);
}
nbcc = 0;
dfs_ap(0, 1);
For(i, 0, nbcc - 1) {
// cout << sz(bcc[i]) << ":";
for(auto &j:bcc[i]) {
// cout << " " << j;
link_tr(n + i, j);
}
// cout << "\n";
}
// return vector<int>(n, 0);
dfs_siz(0, -1, n);
for(auto &e:edge) {
int s = e.F;
int t = e.S;
if(siz[s] < siz[t]) swap(s, t);
// s is parent
int s1 = siz[t];
int s2 = n - s1;
if(s1 > s2) {
swap(s1, s2);
swap(s, t);
}
// size of t's side is smaller (s1)
if(s1 >= x && s2 >= y) {
// cout << s << " " << t << "\n";
int i1 = get_id(x);
vector<int> v1 = comp(t, s, x, n);
int i2 = get_id(y);
vector<int> v2 = comp(s, t, y, n);
int i3 = 6 - i1 - i2;
vector<int> res(n, i3);
for(auto &i:v1) res[i] = i1;
for(auto &i:v2) res[i] = i2;
return res;
}
}
return vector<int>(n, 0);
}
