#include <bits/stdc++.h>
#include "split.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, A, B, fo = -1, fox;
int siz[N];
bool bio[N];
vector <int> no;
vector <int> adj[N];
void ldfs(int x) {
bio[x] = 1;
no.push_back(x);
for (auto y : adj[x]) {
if (bio[y]) continue;
ldfs(y);
}
}
void dfs(int x) {
bio[x] = 1;
siz[x] = 1;
vector <int> v;
for (auto y : adj[x]) {
if (bio[y]) continue;
dfs(y);
siz[x] += siz[y];
v.push_back(siz[y]);
}
if (siz[x] != n) v.push_back(n-siz[x]);
sort(all(v));
if (v.back() >= B) {
if (n-v.back() >= A) {
fo = 0;
fox = x;
}
}
else {
if (v.back() >= A) {
fo = 1;
fox = x;
}
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
n = nn;
int m = p.size();
vector <int> res(n, 0);
for (int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
int mxdeg = 0;
for (int i = 0; i < n; i++) mxdeg = max(mxdeg, (int)adj[i].size());
if (mxdeg <= 2) {
ldfs(0);
for (int i = 0; i < a; i++) res[no[i]] = 1;
for (int i = a; i < a+b; i++) res[no[i]] = 2;
for (int i = a+b; i < n; i++) res[no[i]] = 3;
}
else if (a == 1) {
ldfs(0);
for (int i = 0; i < b; i++) res[no[i]] = 2;
for (int i = b; i < n-1; i++) res[no[i]] = 3;
res[no[n-1]] = 1;
}
else if (n == m+1) {
vector <pair <int, int> > op = {{a, 1}, {b, 2}, {c, 3}}; sort(all(op));
a = op[0].F; b = op[1].F; c = op[2].F;
A = a; B = b;
dfs(0);
if (fo == -1) return res;
for (int i = 0; i < n; i++) res[i] = op[2].S;
int x = fox, o = fo;
memset(bio, 0, sizeof bio);
dfs(x);
vector <pair <int, int> > v;
for (auto y : adj[x]) {
v.push_back({siz[y], y});
}
sort(all(v));
memset(bio, 0, sizeof bio);
if (o == 0) {
bio[x] = 1;
ldfs(v.back().S);
for (int i = 0; i < b; i++) res[no[i]] = op[1].S;
no.clear();
ldfs(x);
for (int i = 0; i < a; i++) res[no[i]] = op[0].S;
}
else {
bio[x] = 1;
ldfs(v.back().S);
for (int i = 0; i < a; i++) res[no[i]] = op[0].S;
no.clear();
ldfs(x);
for (int i = 0; i < b; i++) res[no[i]] = op[1].S;
}
}
return res;
}
