#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<pair<int,int>> poss = {{a,1},{b,2},{c,3}};
sort(poss.begin(), poss.end());
vector<vector<int>> fulladj(n);
for(int i=0;i<p.size();i++)fulladj[p[i]].emplace_back(q[i]);
for(int i=0;i<p.size();i++)fulladj[q[i]].emplace_back(p[i]);
pair<int,int> answer = {-1,-1};
for(int root=0;root<n;root++){
vector<vector<int>> adj(n);
vector<bool> visited(n);
function<void(int,int)> adjcreate = [&](int x,int p) {
if(visited[x])return;
if(p!=-1) {
adj[p].emplace_back(x);
adj[x].emplace_back(p);
}
visited[x]=true;
for(int&i:fulladj[x])adjcreate(i,x);
};
adjcreate(root,-1);
bool reiter = false;
back:
function<int(int,int)> dfs = [&](int x,int p) {
int subsize = 1;
for(int&i:adj[x])if(i!=p)subsize+=dfs(i,x);
if(subsize>=poss[0].first and n-subsize>=poss[1].first)answer={x,p};
return subsize;
};
dfs(0,-1);
if(answer.first==-1) {
if(reiter) {
swap(poss[1],poss[0]);
continue;
}
reiter = true;
swap(poss[1],poss[0]);
goto back;
}
{
vector<int> res(n,2);
int curr = 0;
int currnode = 0;
int tar = 0;
function<void(int,int)> dfs = [&](int x,int p) {
if(curr==tar)return;
res[x]=currnode;
curr++;
for(int&i:adj[x])if(i!=p)dfs(i,x);
};
curr = 0;
currnode = 0;
tar = poss[0].first;
dfs(answer.first,answer.second);
curr = 0;
currnode = 1;
tar = poss[1].first;
dfs(answer.second,answer.first);
for(int&i:res)i=poss[i].second;
return res;
}
}
return vector<int>(n);
}
