#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int N = 100005;
int n, a, b, c;
vector <int> C, adj[N];
int sz[N], check[N];
void dfs(int u, int p)
{
sz[u] = 1;
check[u] = 1;
for (auto v: adj[u])
{
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
if (sz[v] >= a) check[u] = 0;
}
if (sz[u] < a || n - sz[u] < a) check[u] = 1;
}
void color(int u, int num, int cl)
{
queue <int> q;
q.push(u);
C[u] = cl;
int cnt = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto v: adj[u])
if (!C[v])
{
++cnt;
C[v] = cl;
q.push(v);
if (num == cnt) return;
}
}
}
vector <int> find_split(int _n, int _a, int _b, int _c, vector <int> u, vector <int> v)
{
n = _n;
a = _a, b = _b, c = _c;
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
int m = (int)v.size();
C = vector <int> (n, 0);
for (int i = 0; i < m; i ++)
{
adj[v[i]].push_back(u[i]);
adj[u[i]].push_back(v[i]);
}
for (int u = 1; u < n; ++u)
if (check[u])
{
if (sz[u] <= n - sz[u])
{
color(u, a, 1);
color(0, b, 2);
}
else
{
color(u, b, 1);
color(0, a, 2);
}
for (int i = 0; i < n; ++i)
if (!C[i]) C[i] = 3;
return C;
}
return C;
}
