#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int c1, int c2, int c3, vector<int> p, vector<int> q) {
pair<int, int>C[3] = {{c1, 1}, {c2, 2}, {c3, 3}};
sort(C, C + 3);
vector<int> res(n, C[2].second);
int pa[n];
function<int(int)>root = [&](int x)
{
if (x == pa[x])
return x;
return pa[x] = root(pa[x]);
};
vector<int>adj[n];
vector<int>kaim[n];
vector<int>child[n];
for (int i = 0; i < (int)p.size(); i++)
{
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
for (int i = 0; i < n; i++)
{
for (int j : adj[i])
{
int a = root(i);
int b = root(j);
if (a != b)
{
pa[a] = b;
kaim[i].push_back(j);
kaim[j].push_back(i);
}
}
}
vector<bool>vis(n, false);
int sz[n];
function<void(int)>dfs0 = [&](int x)->void
{
vis[x] = true;
sz[x] = 1;
for (int y : kaim[x])
{
if (!vis[y])
{
child[x].push_back(y);
dfs0(y);
sz[x] += sz[y];
}
}
};
dfs0(0);
int gal = -1;
int col = -1;
pair<int, int>cen = {n + 1, 0};
function<void(int)>dfs1 = [&](int x)->void
{
int mx = n - sz[x];
for (int y : child[x])
{
mx = max(mx, sz[y]);
dfs1(y);
if (sz[y] >= C[1].first && n - sz[y] >= C[0].first)
{
gal = y;
col = 1;
}
if (sz[y] >= C[0].first && n - sz[y] >= C[1].first)
{
gal = y;
col = 0;
}
}
cen = min(cen, {mx, x});
};
dfs1(0);
assert(cen.first * 2 <= n);
if (gal == -1)
{
int c = cen.second;
vector<int>com(n, 1);
com[c] = 0;
int timer = 2;
if (sz[c] == n)
timer = 1;
vector<int>dyd(n, 0);
for (int a : child[c])
{
function<void(int)>dfs2 = [&](int x)->void
{
com[x] = timer;
for (int y : child[x])
{
dfs2(y);
}
};
dfs2(a);
timer++;
}
assert(timer <= n);
for (int i = 0; i < n; i++)
dyd[com[i]]++;
for (int i = 0; i < n; i++)
pa[i] = i;
for (int i = 0; i < n; i++)
{
assert(dyd[i] < C[0].first || dyd[i] > C[1].first);
}
int spalv[n];
for (int i = 0; i < n; i++)
{
for (int j : adj[i])
{
int a = root(com[i]);
int b = root(com[j]);
if (a != b && a != 0 && b != 0)
{
pa[a] = b;
dyd[b] += dyd[a];
if (dyd[b] >= C[0].first)
{
int cnt0 = 0;
int cnt1 = 0;
for (int i = 0; i < n; i++)
{
if (root(com[i]) == b)
{
spalv[i] = 0;
cnt0++;
}
else
{
spalv[i] = 1;
cnt1++;
}
}
int k0 = 0;
int k1 = 0;
if (cnt0 >= C[0].first && cnt1 >= C[1].first)
{
while (spalv[k0] != 0)
k0++;
while (spalv[k1] != 1)
k1++;
}
else if (cnt1 >= C[0].first && cnt0 >= C[1].first)
{
while (spalv[k0] != 1)
k0++;
while (spalv[k1] != 0)
k1++;
}
assert(k0 != k1);
function<void(int, int, int&)>dfs3 = [&](int x, int col, int &cnt)->void
{
if (cnt <= 0)
return;
cnt--;
res[x] = C[col].second;
for (int y : adj[x])
{
if (spalv[y] != spalv[x])
continue;
if (res[y] == C[2].second)
dfs3(y, col, cnt);
}
};
dfs3(k0, 0, C[0].first);
dfs3(k1, 1, C[1].first);
return res;
}
}
}
}
return vector<int>(n, 0);
}
function<void(int, int, int&)>dfs2 = [&](int x, int col, int &cnt)->void
{
if (cnt <= 0)
return;
cnt--;
res[x] = C[col].second;
for (int y : child[x])
{
if (y == gal)
continue;
dfs2(y, col, cnt);
}
};
dfs2(gal, col, C[col].first);
dfs2(0, 1 - col, C[1 - col].first);
return res;
}
// int main()
// {
// for (int i : find_split(9, 3, 3, 3, {0, 1, 2, 3, 4, 5, 6, 7, 8}, {8, 0, 1, 2, 3, 4, 5, 6, 7}))
// {
// cout << i << " ";
// }
// }
