#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int>adj[N], r_adj[N];
int col[N], c[3], val[3], lst = 0;
bool visited[N];
int deg[N], sz[N], root = -1, A, B, NN, W[N], comp[N], CC, tin[N], fup[N], timer;
vector<int>comps[N];
set<pair<int, int>> bridges;
void dfs0(int node, int parent) {
tin[node] = fup[node] = ++timer;
visited[node] = 1;
for (auto i : adj[node]) {
if (i == parent) continue;
if (visited[i]) {
fup[node] = min(fup[node], tin[i]);
}
else {
dfs0(i, node);
fup[node] = min(fup[node], fup[i]);
if (fup[i] > tin[node]) {
bridges.insert({ i, node });
bridges.insert({ node, i });
}
}
}
}
void dfs_comp(int node, int CCC) {
comp[node] = CCC;
comps[CCC].push_back(node);
visited[node] = 1;
for (auto i : adj[node]) {
if (visited[i]) continue;
if (bridges.find({ node, i }) != bridges.end()) {
continue;
}
dfs_comp(i, CCC);
}
}
void dfs(int node, int parent) {
sz[node] = W[node];
for (auto i : adj[node]) {
if (i == parent) continue;
dfs(i, node);
sz[node] += sz[i];
}
}
bool mi_gagatov = 0;
int gagat = -1;
bool can_split(int node, int parent) {
if (W[node] >= A + B) {
gagat = node;
mi_gagatov = 1;
return 1;
}
vector<int> v;
for (auto i : adj[node]) {
v.push_back(sz[i]);
}
if (v.size() > 1) {
sort(v.rbegin(), v.rend());
int K = 0;
for (auto i : v) {
if (i >= A) {
K = i;
}
}
if (K != 0 && sz[node] - K >= B) {
root = node;
return 1;
}
}
for (auto i : adj[node]) {
if (i == parent) continue;
int P = sz[i];
sz[i] = sz[node];
sz[node] = sz[node] - P;
if (can_split(i, node)) {
return 1;
}
sz[node] += P;
sz[i] = P;
}
return 0;
}
void dfs_col(int node, int parent, int compo) {
if (c[compo] == val[compo]) return;
for (auto i : comps[node]) {
c[compo]++;
col[node] = compo;
if (c[compo] == val[compo]) break;
}
visited[node] = 1;
for (auto i : adj[node]) {
if (i == parent || visited[i]) continue;
dfs_col(i, node, compo);
}
}
void dfs_col_mi_gagatov(int node, int compo) {
if (c[compo] == val[compo]) return;
c[compo]++;
col[node] = compo + 1;
visited[node] = 1;
for (auto i : r_adj[node]) {
if (visited[i] || bridges.find({ i, node }) != bridges.end()) continue;
dfs_col_mi_gagatov(i, compo);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res;
NN = n;
for (int i = 0; i < p.size(); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
r_adj[p[i]].push_back(q[i]);
r_adj[q[i]].push_back(p[i]);
deg[p[i]]++;
deg[q[i]]++;
}
dfs0(0, 0);
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
CC++;
dfs_comp(i, CC);
}
for (int i = 0; i < n; i++) {
W[comp[i]]++;
}
vector<pair<int, int>> edges;
for (int i = 0; i < n; i++) {
for (auto j : adj[i]) {
if (comp[i] != comp[j]) {
edges.push_back({ comp[i], comp[j] });
}
}
}
for (int i = 0; i < n; i++) {
sort(r_adj[i].begin(), r_adj[i].end(), [&](int u, int v) {
return deg[u] < deg[v];
});
adj[i].clear();
}
for (auto [u, v] : edges) {
adj[u].push_back(v);
}
for (int i = 1; i <= CC; i++) {
cerr << W[i] << endl;
cerr << "adj[" << i << "] = [ ";
for (auto j : adj[i]) cerr << j << ' ';
cerr << "]\n";
}
vector<pair<int, int>>o;
o.push_back({ a, 0 });
o.push_back({ b, 1 });
o.push_back({ c, 2 });
sort(o.begin(), o.end());
A = o[0].first;
B = o[1].first;
val[0] = a;
val[1] = b;
val[2] = c;
dfs(1, 0);
if (!can_split(1, 0)) {
for (int i = 0; i < n; i++) {
res.push_back(0);
}
return res;
}
if (mi_gagatov) {
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
int g = -1;
for (int i = 0; i < n; i++) {
if (comp[i] == gagat && (g == -1 || deg[i] < deg[g])) {
g = i;
}
}
dfs_col_mi_gagatov(g, o[0].second);
for (int i = 0; i < n; i++) {
if (comp[i] == gagat && !visited[i]) {
g = i;
}
}
dfs_col_mi_gagatov(g, o[1].second);
cerr << "!\n";
for (int i = 0; i < n; i++) {
if (col[i]) {
res.push_back(col[i]);
}
else {
res.push_back(o[2].second + 1);
}
}
return res;
}
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
dfs(root, -1);
vector<pair<int, int>> v;
for (auto i : adj[root]) {
v.push_back({ sz[i], i });
}
sort(v.rbegin(), v.rend());
int pr = -1;
for (auto i : v) {
if (i.first >= A) {
pr = i.second;
}
}
dfs_col(pr, root, o[0].second);
dfs_col(root, -1, o[1].second);
for (int i = 0; i < n; i++) {
if (!col[i]) {
col[i] = o[2].second + 1;
}
}
for (int i = 0; i < n; i++) {
res.push_back(col[i]);
}
return res;
}
