#include "split.h"
#include<bits/stdc++.h>
using namespace std;
bool odw[100010];
vector<int>graf[100010];
int a, b, c, n;
int low[100010];
int r[100010];
int dep[100010];
int ojciec[100010];
bool NIE_DA_SIE;
int root2 = -1;
int root[100010];
void dfs(int x){
r[x] = 1;
odw[x] = 1;
low[x] = dep[x];
int przeciwne = 0;
vector<int>synowie;
for(auto j: graf[x]){
if(!odw[j]){
synowie.push_back(j);
dfs(j);
if(root2!=-1)return;
if(NIE_DA_SIE)return;
r[x]+=r[j];
low[x] = min(low[x], low[j]);
if(low[j]<dep[x])
przeciwne+=r[j];
}
else{
low[x] = min(low[x], dep[j]);
}
}
if(r[x]<a)return;
if(r[x]-przeciwne<=n-a){//da sie
for(auto j: synowie){
if(r[x]<=n-a)break;
ojciec[j] = ojciec[x];
r[x]-=r[j];
}
ojciec[x] = -1;
root2 = x;
return;
}
if(r[x]-przeciwne>n-a){//nie da sie
NIE_DA_SIE = 1;
return;
}
}
void dfs0(int x){
odw[x] = 1;
for(auto j: graf[x])
if(!odw[j]){
dep[j] = dep[x]+1;
dfs0(j);
ojciec[j] = x;
}
}
void dfs2(int x){
if(ojciec[x]==-1)
root[x] = x;
else
root[x] = root[ojciec[x]];
odw[x] = 1;
for(auto j: graf[x])
if(!odw[j]){
dfs2(j);
}
}
vector<int>zbior[100010];
vector<int>split;
int rozmiar;
void dfs3(int x, int war){
odw[x] = 1;
if(war==0){
if(rozmiar<a){
split[x] = 0;
rozmiar++;
}
else
split[x] = 2;
}
else{
if(rozmiar<b){
split[x] = 1;
rozmiar++;
}
else
split[x] = 2;
}
for(auto j: graf[x])
if(!odw[j])
dfs3(j, war);
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
n = N, a = A, b = B, c = C;
int m = p.size(), i;
ojciec[0] = -1;
pair<int,int> rozmiary[3] = {{a, 1},{b,2},{c, 3}};
sort(rozmiary, rozmiary+3);
a = rozmiary[0].first, b = rozmiary[1].first, c = rozmiary[2].first;
for(i=0;i<m;i++){
graf[p[i]].push_back(q[i]);
graf[q[i]].push_back(p[i]);
}
dfs0(0);
for(i=0;i<n;i++)odw[i] = 0;
dfs(0);
vector<int> res(n,0);
if(NIE_DA_SIE)return res;
for(i=0;i<n;i++)odw[i] = 0;
dfs2(0);
for(i=0;i<n;i++)zbior[root[i]].push_back(i);
int root1 = 0;
if(zbior[root1].size()<zbior[root2].size())swap(root1, root2);
for(i=0;i<n;i++)graf[i].clear();
for(i=0;i<m;i++)
if(root[p[i]]==root[q[i]]){
graf[p[i]].push_back(q[i]);
graf[q[i]].push_back(p[i]);
}
for(i=0;i<n;i++)odw[i] = 0;
split.resize(n);
rozmiar = 0;
dfs3(root2, 0);//szukam a
rozmiar = 0;
dfs3(root1, 1);//szukam b
for(i=0;i<n;i++)
split[i] = rozmiary[split[i]].second;
return split;
}
