#include<bits/stdc++.h>
#include "split.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int INF = 1e9;
const int MX = 1e5+5;
vector<in> edges;
vector<int> adj_G[MX];
vector<int> adj_T[MX];
vector<bool> vis;
vector<int> sub;
void dfs(int u)
{
vis[u] = 1;
for(int v: adj_G[u])
{
if(vis[v])
continue;
adj_T[u].pb(v);
adj_T[v].pb(u);
dfs(v);
sub[u]+=sub[v];
}
return;
}
int centroid(int u, int p, int sz)
{
for(int v: adj_T[u])
{
if(v==p) continue;
if(2*sub[v] >= sz)
return centroid(v, u, sz);
}
return u;
}
vector<int> pa;
int leader(int u)
{
if(pa[u] < 0)
return u;
else
return pa[u] = leader(pa[u]);
}
int merge(int u, int v)
{
u = leader(u);
v = leader(v);
if(u == v)
return 0;
if(pa[u] < pa[v])
swap(u, v);
pa[v]+=pa[u];
pa[u] = v;
return -pa[v];
}
int rep(int u, int p)
{
int ret = 1;
for(int v: adj_T[u])
{
if(v==p) continue;
merge(u, v);
ret+=rep(v, u);
}
return ret;
}
vector<bool> SPLIT;
void perform(int u, bool typ, int cnt, int val, vector<int> &ans, int &cur)
{
/*cout << "size restriction to " << cnt << endl;
cout << "reached cur = " << cur << endl;*/
vis[u] = 1;
ans[u] = val;
cur++;
if(cur == cnt)
return;
for(int v: adj_G[u])
{
if(vis[v]) continue;
if(SPLIT[v] != typ) continue;
perform(v, typ, cnt, val, ans, cur);
if(cur == cnt)
return;
}
return;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
vector<in> pp = {{a, 1}, {b, 2}, {c, 3}};
sort(pp.begin(), pp.end());
vector<int> ans(n, 0);
edges.clear();
for(int i = 0; i < n; i++)
{
adj_G[i].clear();
adj_T[i].clear();
}
int m = p.size();
for(int i = 0; i < m; i++)
{
edges.pb({p[i], q[i]});
adj_G[p[i]].pb(q[i]);
adj_G[q[i]].pb(p[i]);
}
sub.assign(n, 1);
vis.assign(n, 0);
dfs(0);
int x = centroid(0, -1, n);
pa.assign(n, -1);
SPLIT.assign(n, 0);
bool win = 0;
for(int z: adj_T[x])
{
if(win)
continue;
int s = rep(z, x);
if(s >= pp[0][0])
{
win = 1;
for(int i = 0; i < n; i++)
SPLIT[i] = (leader(i) != leader(z));
}
}
for(auto [xp, y]: edges)
{
if((xp == x) || (y == x))
continue;
int D = merge(xp, y);
if(D >= pp[0][0])
{
win = 1;
for(int i = 0; i < n; i++)
SPLIT[i] = (leader(i) != leader(y))^(((2*D) >= n));
break;
}
}
if(!win)
return ans;
for(int k = 0; k < 2; k++)
{
int j = 0;
while(SPLIT[j] != k)
j++;
vis.assign(n, 0);
int help = 0;
perform(j, k&1, pp[k][0], pp[k][1], ans, help);
}
for(int i = 0; i < n; i++)
{
if(ans[i]) continue;
ans[i] = pp[2][1];
}
return ans;
}
/*signed main()
{
vector<int> ans = find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});
vector<int> sk[4];
for(int i = 0; i < ans.size(); i++)
sk[ans[i]].pb(i);
for(int j = 1; j <= 3; j++)
{
cout << "The group of j = " << j << endl;
for(auto s: sk[j])
cout << s << " ";
cout << endl;
}
return 0;
}*/
