#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "split.h"
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 1e5 + 5;
int n;
vector<int> siz; // velkosti podstromov
vector<vector<int> > g; // ten strom
void dfs_siz(int u)
{
siz[u] = 1;
for (int v : g[u]) if (!siz[v]) dfs_siz(v), siz[u] += siz[v];
}
int centroid()
{
dfs_siz(0);
for (int i = 0; i < n; i++)
{
if ((n - siz[i]) > n / 2) continue;
bool bad = false;
for (int j : g[i]) if (siz[j] < siz[i] && siz[j] > n / 2) bad = true;
if (!bad) return i;
}
//cout << "WA\n";
}
vector<int> pr, s; // unionfind stuff
void reset() { for (int i = 0; i < n; i++) pr[i] = i, s[i] = 1; }
int root(int a) { return pr[a] == a ? a : pr[a] = root(pr[a]); }
bool merge(int a, int b)
{
a = root(a), b = root(b);
if (a == b) return false;
pr[a] = b, s[b] += s[a];
return true;
}
vector<int> ans;
void dfs_color(int u, int cl1, int cl2, int &cnt)
{
if (cnt) ans[u] = cl1, cnt--;
else ans[u] = cl2;
for (int v : g[u]) if (!ans[v]) dfs_color(v, cl1, cl2, cnt);
}
void color(vector<int> cm, int cl1, int cl2, int cnt, const vector<int> &p, const vector<int> &q)
{
set<int> s(cm.begin(), cm.end());
g.assign(n, {});
for (int i = 0; i < p.size(); i++) if (s.count(p[i]) && s.count(q[i])) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
dfs_color(cm[0], cl1, cl2, cnt);
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
vector<pair<int, int> > col = { {a, 1}, {b,2}, {c,3} };
sort(col.begin(), col.end());
int m = col[0].first;
n = N, ans.assign(n, 0), siz.assign(n, 0), g.assign(n, {}), pr.assign(n, -1), s.assign(n, -1);
reset();
vector<int> strom, other;
for (int i = 0; i < p.size(); i++)
{
if (merge(p[i], q[i])) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]), strom.push_back(i);
else other.push_back(i);
}
if (strom.size() != n - 1) return ans;
int vr = centroid();
reset();
for (int i : strom) if (p[i] != vr && q[i] != vr) merge(p[i], q[i]);
for (int i : other) if (p[i] != vr && q[i] != vr)
{
int a = root(p[i]), b = root(q[i]);
if (s[a] < m && s[b] < m) merge(a, b);
}
int big = -1;
for (int i = 0; i < n; i++) if (pr[i] == i && s[i] >= m) big = i;
if (big == -1)
return ans;
vector<vector<int> > v(2);
for (int i = 0; i < n; i++) v[root(i) == big].push_back(i);
if (v[0].size() > v[1].size()) swap(v[0], v[1]);
for (int i = 0; i < 2; i++) color(v[i], col[i].second, col[2].second, col[i].first, p, q);
return ans;
}
