#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;
int n, m;
vector<int> g[N];
int q[N];
int p0[N];
void dfs0(int x, int p)
{
p0[x] = p;
q[x] = 1;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (h == p)
continue;
dfs0(h, x);
q[x] += q[h];
}
}
pair<int, int> u[4];
vector<int> ans;
void dfs(int x, int p, int y)
{
if (ans[x - 1])
return;
if (!u[y].fi)
return;
ans[x - 1] = u[y].se;
--u[y].fi;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (h == p)
continue;
dfs(h, x, y);
}
}
vector<int> find_split(int N_, int A, int B, int C, vector<int> P, vector<int> Q)
{
n = N_;
m = sz(P);
for (int i = 0; i < m; ++i)
{
int x = P[i];
int y = Q[i];
++x;
++y;
g[x].push_back(y);
g[y].push_back(x);
}
u[1] = m_p(A, 1);
u[2] = m_p(B, 2);
u[3] = m_p(C, 3);
sort(u + 1, u + 3 + 1);
if (u[1].fi == 1)
{
ans.assign(n, 0);
dfs(1, 1, 2);
for (int x = 0; x < n; ++x)
{
if (!ans[x])
{
ans[x] = u[1].se;
break;
}
}
for (int x = 0; x < n; ++x)
{
if (!ans[x])
ans[x] = u[3].se;
}
return ans;
}
dfs0(1, 1);
for (int x = 1; x <= n; ++x)
{
if (u[1].fi <= min(q[x], n - q[x]) && u[2].fi <= max(q[x], n - q[x]))
{
ans.assign(n, 0);
if (q[x] < n - q[x])
{
dfs(x, p0[x], 1);
dfs(p0[x], x, 2);
}
else
{
dfs(x, p0[x], 2);
dfs(p0[x], x, 1);
}
for (int i = 0; i < n; ++i)
{
if (!ans[i])
ans[i] = u[3].se;
}
return ans;
}
}
ans.assign(n, 0);
return ans;
}
