#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define uwu return
#define fs first
#define sc second
#define all(x) x.begin(), x.end()
mt19937 rng(time(0));
const int SIZE = 1e5 + 5;
vector <int> graph[SIZE];
bitset <SIZE> been;
vector <int> dfs_tree;
bool flag = 0;
int dfs(int n, int a, int b, int nd){
int ret = 1;
been[nd] = 1;
dfs_tree.push_back(nd);
// cerr << nd << '\n';
for (auto i : graph[nd]){
if(!been[i]){
int tmp = dfs(n, a, b, i);
if(tmp >= a && n - tmp >= b)
flag = 1;
if(tmp >= b && n - tmp >= a)
flag = 1;
ret += tmp;
}
}
dfs_tree.push_back(nd);
uwu ret;
}
int u, v;
int find_ans(int n, int a, int b, int nd){
int ret = 1;
been[nd] = 1;
for (auto i : graph[nd]){
if(!been[i]){
int tmp = find_ans(n, a, b, i);
if(tmp == -1)
return -1;
if (tmp >= a && n - tmp >= b){
v = i;
u = nd;
flag = 0;
return -1;
}
if(tmp >= b && n - tmp >= a){
v = i;
u = nd;
flag = 1;
return -1;
}
ret += tmp;
}
}
uwu ret;
}
const double TIME_LIMIT = 1.9;
vector <int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = q.size();
for (int i = 0; i < m; i++){
graph[q[i]].push_back(p[i]);
graph[p[i]].push_back(q[i]);
}
vector <pair<int, int>> order = {{a, 1}, {b, 2}, {c, 3}};
sort(all(order));
auto ck = clock();
int rt = 0;
for (; (double)(clock() - ck) / CLOCKS_PER_SEC < TIME_LIMIT;){
for (int i = 0; i < n; i++){
shuffle(all(graph[i]), rng);
}
rt = rng() % n;
been.reset();
dfs_tree.clear();
dfs(n, order[0].fs, order[1].fs, rt);
if(flag)
break;
}
// cerr << "hi\n";
if (!flag)
uwu vector<int>(n, 0);
been.reset();
find_ans(n, order[0].fs, order[1].fs, rt);
vector <int> splitted_tree[2];
int nw = 0;
for (int i = 0; i < (int)dfs_tree.size(); i++){
if(dfs_tree[i] == v && !nw){
nw = nw ^ 1;
splitted_tree[nw].push_back(dfs_tree[i]);
}
else if(dfs_tree[i] == v && nw){
splitted_tree[nw].push_back(dfs_tree[i]);
nw = nw ^ 1;
}
else{
splitted_tree[nw].push_back(dfs_tree[i]);
}
}
vector <int> ret(n);
if(!flag)
swap(splitted_tree[0], splitted_tree[1]);
int ptr = 0;
// for(auto i:dfs_tree){
// cerr << i << ' ';
// }
// cerr << '\n';
for (auto i : splitted_tree[0]){
// cerr << i << ' ';
if(ptr >= order[0].fs)
continue;;
if (!ret[i]){
ret[i] = order[0].sc;
ptr++;
}
}
// cerr << '\n';
ptr = 0;
for (auto i : splitted_tree[1]){
// cerr << i << ' ';
if(ptr >= order[1].fs)
continue;;
if (!ret[i]){
ret[i] = order[1].sc;
ptr++;
}
}
// cerr << '\n';
for (auto &i : ret){
if(!i)
i = order[2].sc;
}
uwu ret;
}
