#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 100 * 1000 + 7;
bool vis[N];
int wys[N], low[N], il[N];
vector<int> answer;
int tab[N];
pair<int, int> cls[3];
bool dcl[3];
vector<int> ed[N];
pair<int, int> bst = make_pair(N * 2, -1);
void DFS(int v)
{
low[v] = wys[v]; il[v] = 1;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(il[ed[v][i]])
{
low[v] = min(low[v], wys[ed[v][i]]);
continue;
}
wys[ed[v][i]] = wys[v] + 1;
DFS(ed[v][i]);
il[v] += il[ed[v][i]];
low[v] = min(low[v], low[ed[v][i]]);
}
//cerr << "dfs: " << v << " " << wys[v] << " " << il[v] << "\n";
for(int i = 0; i < 2; ++i)
if(cls[i].st <= il[v])
bst = min(bst, make_pair(il[v] - cls[i].st, v));
}
void DFST(int v, int clr, int &lft)
{
if(lft == 0) return;
vis[v] = true;
--lft;
answer[v] = clr;
//cerr << "dfst: " << v << " " << clr << " " << lft << "\n";
for(int i = 0; i < (int)ed[v].size(); ++i)
if(!vis[ed[v][i]] && wys[ed[v][i]] > wys[v])
DFST(ed[v][i], clr, lft);
}
vector<int> find_split(int n, int Xa, int Xb, int Xc, vector<int> p, vector<int> q)
{
cls[0] = make_pair(Xa, 1); cls[1] = make_pair(Xb, 2); cls[2] = make_pair(Xc, 3);
sort(cls, cls + 3);
//for(int i = 0; i < 3; ++i)
//cerr << "bst: " << cls[i].st << " " << cls[i].nd << "\n";
for(int i = 0; i < n; ++i) answer.pb(0);
for(int i = 0; i < (int)p.size(); ++i)
{
ed[p[i]].pb(q[i]);
ed[q[i]].pb(p[i]);
}
DFS(0);
int xd;
//cerr << "bst: " << bst.nd << "\n\n";
if(il[bst.nd] >= cls[1].st && n - il[bst.nd] >= cls[0].st)
{
xd = cls[1].st;
DFST(bst.nd, cls[1].nd, xd);
xd = cls[0].st;
DFST(0, cls[0].nd, xd);
for(int i = 0; i < n; ++i)
if(answer[i] == 0)
answer[i] = cls[2].nd;
return answer;
}
if(n - il[bst.nd] >= cls[1].st)
{
xd = cls[0].st;
DFST(bst.nd, cls[0].nd, xd);
xd = cls[1].st;
DFST(1, cls[1].nd, xd);
for(int i = 0; i < n; ++i)
if(answer[i] == 0)
answer[i] = cls[2].nd;
return answer;
}
int v = bst.nd;
int s = n - il[v];
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(wys[ed[v][i]] < wys[v] || low[ed[v][i]] >= wys[v]) continue;
s += il[ed[v][i]];
}
if(s < cls[0].st)
return answer;
xd = cls[0].st;
vis[v] = true;
DFST(0, cls[0].nd, xd);
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(wys[ed[v][i]] < wys[v] || low[ed[v][i]] >= wys[v]) continue;
DFST(ed[v][i], cls[0].nd, xd);
}
xd = cls[1].st;
DFST(v, cls[1].nd, xd);
for(int i = 0; i < n; ++i)
if(answer[i] == 0)
answer[i] = cls[2].nd;
return answer;
}
