#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int a, b, c, n;
int colSz[4];
const int N = 200005;
vector<int> res;
vector<int> adj[N];
int good[N];
void colour(int node, int par, int& cur, int col)
{
if (cur == 0) return;
res[node] = col;
cur--;
for (int next : adj[node])
{
if (next == par) continue;
colour(next, node, cur, col);
}
}
void colour2(int node, int& cur, int col)
{
if (cur == 0) return;
res[node] = col;
cur--;
for (int next : adj[node])
{
if (res[node] != 0) continue;
colour2(next, cur, col);
}
}
int sz[N];
void dfs(int node, int par)
{
sz[node] = 1;
for (int next : adj[node])
{
if (next == par) continue;
dfs(next, node);
sz[node] += sz[next];
}
}
void findGood(int node, int par)
{
if (res[0] != 0) return;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
if (i == j) continue;
if (sz[node] >= colSz[i] && n - sz[node] >= colSz[j])
{
colour(node, par, colSz[i], i);
colour(par, node, colSz[j], j);
int k = 1;
for (; k == i || k == j; k++);
for (int l = 0; l < n; l++) if (res[l] == 0) res[l] = k;
return;
}
}
}
for (int next : adj[node])
{
if (next == par) continue;
findGood(next,node);
}
}
vector<int> find_split(int n1, int A, int B, int C, vector<int> P, vector<int> Q) {
n = n1;
a =A;
b = B;
c = C;
colSz[1] = a;
colSz[2] = b;
colSz[3] = c;
res.resize(n);
for (int i = 0; i < P.size(); i++)
{
adj[P[i]].push_back(Q[i]);
adj[Q[i]].push_back(P[i]);
}
if (P.size() == n - 1)
{
dfs(0, -1);
findGood(0, -1);
} else if (a == 1)
{
colour2(0, colSz[2], 2);
for (int i = 0; i < n; i++)
{
if (res[i] == 0)
{
res[i] = 1;
break;
}
}
for (int i = 0; i < n; i++)
{
if (res[i] == 0)
{
res[i] = 3;
}
}
}
return res;
}
/*
11 10
2 5 4
0 1
1 2
1 3
3 4
3 5
6 7
6 8
0 6
8 9
8 10
*/
