#include "split.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int m, deg[maxn];
vector < int > g[maxn];
int used[maxn];
int sub[maxn], par[maxn], ver = 0, all;
int in, out;
int c1, c2, c3;
int col1, col2, col3;
void dfs(int beg, int from)
{
used[beg] = 1;
sub[beg] = 1;
for (auto nb: g[beg])
{
if(used[nb])continue;
if(nb == from)continue;
dfs(nb, beg);
par[nb] = beg;
sub[beg] += sub[nb];
}
if(sub[beg] >= c1 && all-sub[beg] >= c1)
{
ver = beg;
in = sub[beg];
out = all-sub[beg];
}
}
int track[maxn];
int broika;
void rec(int beg, int from, int cvqt)
{
if(!broika)return;
broika --;
track[beg] = cvqt;
//cout << "gtt " << endl;
for (auto nb: g[beg])
{
if(nb == from)continue;
if(track[nb])continue;
rec(nb, beg, cvqt);
}
}
int cnt = 0;
void rec2(int beg, int from, int cvqt)
{
if(track[beg])return;
cnt ++;
if(!broika)return;
broika --;
track[beg] = cvqt;
for (auto nb: g[beg])
{
if(nb == from)continue;
if(track[nb])continue;
rec2(nb, beg, cvqt);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
m = p.size();
all = n;
ver = -1;
for (int i = 0; i < m; ++ i)
{
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
if(a <= min(b, c))
{
c1 = a;
col1 = 1;
}
else if(b <= min(a, c))
{
c1 = b;
col1 = 2;
}
else if(c <= min(a, b))
{
c1 = c;
col1 = 3;
}
if(1 != col1 && a >= max(b, c))
{
c3 = a;
col3 = 1;
}
else if(2 != col1 && b >= max(a, c))
{
c3 = b;
col3 = 2;
}
else if(3 != col1 && c >= max(a, b))
{
c3 = c;
col3 = 3;
}
col2 = 6 - col1 - col3;
c2 = n - c1 - c3;
assert(c1 + c2 + c3 == n);
assert(col1 >= 1 && col1 <= 3);
assert(col2 >= 1 && col2 <= 3);
assert(col3 >= 1 && col3 <= 3);
dfs(0, -1);
vector < int > ans;
if(ver == -1)
{
for (int i = 1; i <= n; ++ i)
ans.pb(0);
return ans;
}
int pos = ver;
if(out >= c2)
{
broika = c1;
rec(ver, par[pos], col1);
broika = c2;
rec2(par[pos], -1, col2);
for (int j = 0; j < n; ++ j)
if(track[j] == 0)track[j] = col3;
for (int j = 0; j < n; ++ j)
ans.pb(track[j]);
return ans;
}
}
