#include "split.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int m, deg[maxn];
int half;
vector < int > g[maxn];
int used[maxn];
vector < int > path;
int isub[maxn];
void idfs(int beg, int from)
{
isub[beg] = 1;
for (auto nb: g[beg])
{
if(nb == from)continue;
idfs(nb, beg);
isub[beg] += isub[nb];
}
}
int find_centoid(int beg, int from)
{
for (auto nb: g[beg])
{
if(nb == from)continue;
if(isub[nb] > half)return find_centoid(nb, beg);
}
return beg;
}
int sub[maxn], p[maxn];
void dfs(int beg, int from)
{
used[beg] = 1;
sub[beg] = 1;
p[beg] = from;
path.pb(beg);
for (auto nb: g[beg])
{
if(used[nb])continue;
dfs(nb, beg);
sub[beg] += sub[nb];
}
}
int c1, c2, c3;
int col1, col2, col3;
int track[maxn];
void rec(int beg, int from)
{
if(!c1)return;
c1 --;
track[beg] = col1;
for (auto nb: g[beg])
{
if(nb == from)continue;
if(track[nb])continue;
rec(nb, beg);
}
}
void rec2(int beg, int from)
{
if(!c2)return;
c2 --;
track[beg] = col2;
for (auto nb: g[beg])
{
if(nb == from)continue;
if(track[nb])continue;
rec2(nb, beg);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
m = p.size();
half = n/2;
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(a != c1 && a >= max(b, c))
{
c3 = a;
col3 = 1;
}
else if(b != c1 && b >= max(a, c))
{
c3 = b;
col3 = 2;
}
else if(c != c1 && c >= max(a, b))
{
c3 = c;
col3 = 3;
}
col2 = 6 - col1 - col3;
c2 = n - c1 - c3;
assert(col1 >= 1 && col1 <= 3);
assert(col2 >= 1 && col2 <= 3);
assert(col3 >= 1 && col3 <= 3);
idfs(0, -1);
int nc = find_centoid(0, -1);
dfs(nc, -1);
vector < int > ans;
int mn = n, pos = 0;
for (int i = 0; i < n; ++ i)
{
if(sub[i] >= c1)
{
mn = min(mn, sub[i]);
if(mn == sub[i])pos = i;
}
}
int outside = n - mn;
if(outside >= c2)
{
rec(pos, p[pos]);
rec2(p[pos], -1);
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;
}
for (int i = 0; i < n; ++ i)
ans.pb(0);
return ans;
}
