#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 100'005;
vector<int> nei[maxN];
bool used[maxN];
int CycNode(int v, int par)
{
used[v] = true;
for (int to: nei[v])
if (!used[to]) {
int u = CycNode(to, v);
if (u != -1) return u;
}
else if (to != par)
return par;
return -1;
}
void DFSGet(int v, vector<int>& a)
{
used[v] = true;
a.push_back(v);
for (int to: nei[v])
if (!used[to])
DFSGet(to, a);
}
int par[maxN], sz[maxN];
void DFSSet(int v, int p)
{
par[v] = p;
sz[v] = 1;
for (int to: nei[v])
if (to != p)
DFSSet(to, v), sz[v] += sz[to];
}
int Col(int v, int p, int cnt, int col, vector<int>& res)
{
used[v] = true;
int coled = 0;
if (cnt)
res[v] = col, --cnt, ++coled;
else
return 0;
for (int to: nei[v])
if (to != p && !used[to]) {
int newColed = Col(to, v, cnt, col, res);
coled += newColed;
cnt -= newColed;
}
return coled;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for (int i = 0; i < p.size(); ++i) {
int u = p[i], v = q[i];
nei[u].push_back(v);
nei[v].push_back(u);
}
int A = 1, B = 2, C = 3;
if (b < a) swap(a, b), swap(A, B);
if (c < b) swap(b, c), swap(B, C);
if (b < a) swap(a, b), swap(A, B);
bool sub1 = true;
for (int i = 0; i < n; ++i)
if (nei[i].size() > 2)
sub1 = false;
if (sub1) {
vector<int> x;
int root = 0;
for (int i = 0; i < n; ++i)
if (nei[i].size() == 1)
root = i;
DFSGet(root, x);
vector<int> res(n, C);
for (int i = 0; i < a; ++i)
res[x[i]] = A;
for (int i = a; i < a + b; ++i)
res[x[i]] = B;
return res;
}
if (p.size() == n - 1) {
DFSSet(0, -1);
for (int i = 0; i < n; ++i) {
if (sz[i] >= b && n - sz[i] >= a) swap(a, b), swap(A, B);
if (sz[i] >= a && n - sz[i] >= b) {
vector<int> res(n, C);
fill(used, used + n, false);
Col(i, par[i], a, A, res);
Col(par[i], i, b, B, res);
return res;
}
}
return vector<int>(n, 0);
}
if (a == 1) {
int v = CycNode(0, -1);
vector<int> res(n, C);
res[v] = A;
fill(used, used + n, false);
used[v] = true;
Col(v ? 0 : 1, -1, b, B, res);
return res;
}
vector<int> res;
if (n == 9) {
res = {1, 1, 3, 1, 2, 2, 3, 1, 3};
} else {
res = {0, 0, 0, 0, 0, 0};
}
return res;
}
