#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
vector<int> G[N];
vector<int> ans;
int colors[] = {1, 2, 3}, sz[N], n, h[N], minh[N], cnt[3];
bool seen[N], colored;
void dfs0(int v)
{
if(cnt[0] == 0 || ans[v] != 0)
return;
//cerr << "dfs0 : " << v << ' ' << colors[0] << endl;
cnt[0]--;
ans[v] = colors[0];
for(int u : G[v])
if(cnt[0] > 0 && h[u] > h[v])
dfs0(u);
}
void dfs1(int v)
{
//cerr << "dfs1 : " << v << ' ' << colors[1] << endl;
cnt[1]--;
ans[v] = colors[1];
for(int u : G[v])
if(cnt[1] > 0 and ans[u] == 0)
dfs1(u);
}
void dfs(int v, int p = N)
{
seen[v] = true;
sz[v] = 1;
h[v] = h[p] + 1;
minh[v] = h[v];
bool t = false;
vector<int> children;
for(int u : G[v])
if(!seen[u])
{
children.push_back(u);
dfs(u, v);
t |= (sz[u] >= cnt[0]);
sz[v] += sz[u];
minh[v] = min(minh[u], minh[v]);
}
else
minh[v] = min(minh[v], h[u]);
if(!t && sz[v] >= cnt[0] && !colored){
// forced size
int fsize = 0;
vector<int> back;
for(int c : children)
if(minh[c] >= h[v])
fsize += sz[c];
else
back.push_back(c);
fsize++; // v itself
while(fsize < cnt[0] && back.size())
{
fsize += sz[back.back()];
back.pop_back();
}
if(fsize >= cnt[1] and n - fsize >= cnt[0])
swap(cnt[1], cnt[0]), swap(colors[0], colors[1]);
if(fsize >= cnt[0] and n - fsize >= cnt[1]){
ans[v] = colors[0];
cnt[0]--;
colored = true;
int p = 0;
for(int u : children)
{
if(p < back.size() and back[p] == u){
p++;
continue;
}
dfs0(u);
}
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
::n = n;
for(int i = 0; i < q.size(); i++)
{
G[q[i]].push_back(p[i]);
G[p[i]].push_back(q[i]);
}
if(a > b)
swap(a, b), swap(colors[0], colors[1]);
if(b > c)
swap(b, c), swap(colors[1], colors[2]);
if(a > b)
swap(a, b), swap(colors[0], colors[1]);
cnt[0] = a, cnt[1] = b, cnt[2] = c;
for(int j = 0; j < 1; j++)
{
ans = vector<int> (n, 0);
dfs(j);
if(colored)
for(int i : ans)
if(i == 0)
{
dfs1(i);
break;
}
if(colored)
for(int &i : ans)
if(i == 0) i = colors[2];
if(colored) break;
}
return ans;
}
