#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
const int MAXN = 2500 + 10;
pll cyc_edge;
vector<int> adjt[MAXN], adj[MAXN], nodes;
int a, b, c, n, m, ans[MAXN], sz[MAXN], T[4] = {0, 1, 2, 3}, ind[MAXN];
bool flag = false;
bool vis[MAXN];
inline bool check(int u, int v) {
return pll(u, v) == cyc_edge || pll(v, u) == cyc_edge;
}
void dfs_ans(int v, int p, int c, int& cnt) {
if (cnt) {
ans[v] = c;
cnt--;
}
for (int u : adj[v]) {
if (u == p || check(u, v)) continue;
dfs_ans(u, v, c, cnt);
}
}
void dfs_tree(int v) {
nodes.push_back(v);
vis[v] = true;
for (int u : adjt[v])
if (!vis[u])
dfs_tree(u), adj[v].push_back(u), adj[u].push_back(v);
}
int dist[MAXN];
void bfs_tree(int v) {
memset(dist, 63, sizeof dist);
queue<int> q;
q.push(v);
dist[v] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
nodes.push_back(v);
for (int u : adj[v]) {
if (dist[u] > dist[v] + 1) {
dist[u] = dist[v] + 1;
q.push(u);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
}
}
void dfs1(int v, int p) {
sz[v] = 1;
for (int u : adj[v]) {
if (u == p || check(u, v)) continue;
dfs1(u, v);
sz[v] += sz[u];
if (!flag && sz[u] >= a && n - sz[u] >= b) {
flag = true;
dfs_ans(u, v, 1, a);
dfs_ans(v, u, 2, b);
}
if (!flag && sz[u] >= b && n - sz[u] >= a) {
flag = true;
dfs_ans(u, v, 2, b);
dfs_ans(v, u, 1, a);
}
}
}
namespace DSU {
int par[MAXN];
inline void init() {
for (int i = 1; i <= n; i++)
par[i] = i;
}
int find(int v) {
return par[v] == v ? v : par[v] = find(par[v]);
}
inline bool unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
par[v] = u;
return true;
}
}
namespace DSU2 {
int par[MAXN];
vector<int> C[MAXN];
set<pll> sz_st;
inline void init() {
sz_st.clear();
for (int i = 1; i <= n; i++)
par[i] = i, C[i] = {i}, sz_st.insert(pll(1, i));
}
inline bool unite(int u, int v) {
u = par[u], v = par[v];
if (u == v) return false;
if (C[u].size() < C[v].size()) swap(u, v);
sz_st.erase(sz_st.find(pll(C[v].size(), v)));
sz_st.erase(sz_st.find(pll(C[u].size(), u)));
for (int e : C[v]) {
par[e] = u;
C[u].push_back(v);
}
sz_st.insert(pll(C[u].size(), u));
C[v].clear();
return true;
}
inline void check() {
if (prev(sz_st.end()) -> X >= b && prev(prev(sz_st.end())) -> X >= a) {
flag = true;
for (int e : C[prev(sz_st.end()) -> Y]) {
if (b) {
b--;
ans[e] = 2;
}
}
for (int e : C[prev(prev(sz_st.end())) -> Y]) {
if (a) {
a--;
ans[e] = 1;
}
}
}
}
}
vector<int> path;
void dfs_path(int v, int p, int tar) {
path.push_back(v);
for (int u : adj[v]) {
if (u == p || check(u, v)) continue;
if (path.back() != tar) dfs_path(u, v, tar);
}
if (path.back() != tar)
path.pop_back();
}
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_;
if (b > c) swap(b, c), swap(T[2], T[3]);
if (a > c) swap(a, c), swap(T[1], T[3]);
if (a > b) swap(a, b), swap(T[1], T[2]);
m = p_.size();
vector<pll> edges;
for (int i = 0; i < m; i++) {
int u = p_[i], v = q_[i];
u++, v++;
adjt[u].push_back(v);
adjt[v].push_back(u);
edges.push_back({u, v});
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int t = 100; // buggy
/* while (t-- && !flag) {
for (int i = 1; i <= n; i++) adj[i].clear();
shuffle(all(edges), rng);
DSU::init();
for (int i = 0; i < m; i++) {
int u = edges[i].X, v = edges[i].Y;
if (DSU::unite(u, v)) adj[u].push_back(v), adj[v].push_back(u);
else cyc_edge = {u, v};
}
path.clear();
if (cyc_edge.X) {
dfs_path(cyc_edge.X, 0, cyc_edge.Y);
adj[cyc_edge.X].push_back(cyc_edge.Y);
adj[cyc_edge.Y].push_back(cyc_edge.X);
for (int i = 0; i < int(path.size()) - 1; i++) {
if (flag) break;
cyc_edge = {path[i], path[i + 1]};
dfs1(1, 0);
}
cyc_edge = {0, 0};
}
}
*/
t = 100;
while (t-- && !flag) {
DSU2::init();
shuffle(all(edges), rng);
for (int k = 1; k < n && !flag; k++) {
DSU2::check();
if (flag) break;
for (auto [u, v] : edges)
if (DSU2::unite(u, v))
break;
}
}
debug(flag)
t = 300;
while (t-- && !flag) {
int v = rng() % n + 1;
for (int i = 1; i <= n; i++)
adj[i].clear(), vis[i] = false, shuffle(all(adjt[i]), rng);
dfs_tree(v);
dfs1(1, 0);
}
t = 150;
while (t-- && !flag) {
int v = rng() % n + 1;
for (int i = 1; i <= n; i++)
adj[i].clear(), shuffle(all(adjt[i]), rng);
bfs_tree(v);
dfs1(1, 0);
}
vector<int> nodes;
for (int i = 1; i <= n; i++)
nodes.push_back(i);
t = 20;
while (t-- && !flag) {
DSU::init();
shuffle(all(nodes), rng);
for (int i = 1; i <= n; i++)
adj[i].clear();
for (int i = 0; i < n; i++) ind[nodes[i]] = i;
for (int i = 0; i < n; i++) {
int mn = -1;
for (int u : adjt[nodes[i]]) {
if (ind[u] > i && (mn == -1 || ind[u] < ind[mn]))
mn = u;
}
if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]), DSU::unite(mn, nodes[i]);
}
shuffle(all(edges), rng);
for (auto [u, v] : edges)
if (DSU::unite(u, v))
adj[u].push_back(v), adj[v].push_back(u);
dfs1(1, 0);
}
t = 20;
while (t-- && !flag) {
nodes.clear();
int v = rng() % n + 1;
for (int i = 1; i <= n; i++)
vis[i] = false, shuffle(all(adjt[i]), rng);
dfs_tree(v);
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 0; i < n; i++) ind[nodes[i]] = i;
for (int i = 0; i < n; i++) {
int mn = -1;
for (int u : adjt[nodes[i]]) {
if (ind[u] > i && (mn == -1 || ind[u] < ind[mn]))
mn = u;
}
if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]);
}
dfs1(1, 0);
}
t = 3000;
while (t-- && !flag) {
nodes.clear();
int v = rng() % n + 1;
for (int i = 1; i <= n; i++)
vis[i] = false, shuffle(all(adjt[i]), rng);
bfs_tree(v);
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 0; i < n; i++) ind[nodes[i]] = i;
for (int i = 0; i < n; i++) {
int mn = -1;
for (int u : adjt[nodes[i]]) {
if (ind[u] > i && (mn == -1 || ind[u] < ind[mn]))
mn = u;
}
if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]);
}
dfs1(1, 0);
}
t = 1000;
while (t-- && !flag) {
nodes.clear();
int v = rng() % n + 1;
for (int i = 1; i <= n; i++)
vis[i] = false, shuffle(all(adjt[i]), rng);
bfs_tree(v);
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 0; i < n; i++) ind[nodes[i]] = i;
for (int i = 0; i < n; i++) {
int mn = -1;
for (int u : adjt[nodes[i]]) {
if (ind[u] > i && (mn == -1 || ind[u] > ind[mn]))
mn = u;
}
if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]);
}
dfs1(1, 0);
}
if (*max_element(ans + 1, ans + n + 1) > 0) {
for (int i = 1; i <= n; i++)
if (ans[i] == 0)
ans[i] = 3;
}
vector<int> res;
for (int i = 1; i <= n; i++)
res.push_back(T[ans[i]]);
return res;
}
