#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MAXN = 100010;
int subtree_size[MAXN];
vector<int> adj[MAXN];
void dfs(int src = 0, int prev = -1) {
//printf("dfs %d %d\n", src, prev);
subtree_size[src] = 1;
for(auto &xt : adj[src]) {
if(xt - prev) {
dfs(xt, src);
subtree_size[src] += subtree_size[xt];
}
}
}
vector<int> get_solution(vector<int> v1, int n1, vector<int> v2, int n2, int n) {
vector<int> ans(n, 6 - n1 - n2);
for(auto &x : v1) {
ans[x] = n1;
}
for(auto &x : v2) {
ans[x] = n2;
}
return ans;
}
bool marked[MAXN];
vector<int> extract(int src, int wrong, int sz) {
for(int i = 0; i < MAXN; i++) {
marked[i] = false;
}
marked[wrong] = true;
vector<int> ans;
stack<int> nodes;
nodes.push(src);
marked[src] = true;
while((int)ans.size() < sz) {
int node = nodes.top();
nodes.pop();
ans.push_back(node);
for(auto &x : adj[node]) {
if(!marked[x]) {
marked[x] = true;
nodes.push(x);
}
}
}
return ans;
}
vector<int> blank(int n) {
vector<int> ans(n, 0);
return ans;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
pair<int, int> arr[] = {{a, 1}, {b, 2}, {c, 3}};
sort(arr, arr + 3);
int A = arr[0].first, B = arr[1].first, C = arr[2].first;
int m = (int)p.size();
for(int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs();
//for(int i = 0; i < n; i++) {
// printf("subtree_size[%d] = %d\n", i, subtree_size[i]);
//}
for(int i = 0; i < m; i++) {
int u = p[i], v = q[i];
if(subtree_size[u] > subtree_size[v]) swap(u, v);
int under = subtree_size[u];
int rest = n - under;
if(under >= A && rest >= A) {
//printf("found for edge %d - %d\n", u, v);
//we've got a solution
vector<int> set_A, set_B;
if(under < rest) {
set_A = extract(u, v, A);
set_B = extract(v, u, B);
} else {
set_A = extract(v, u, A);
set_B = extract(u, v, B);
}
return get_solution(set_A, arr[0].second, set_B, arr[1].second, n);
}
}
//there is no edge connecting two subtrees of sizes >= a
//meaning that it's a star with all subtrees attached of size < a
//in tree, there is no such solution
return blank(n);
}
