#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MN = 1e5 + 5;
vector<int> adj[MN];
bool vis[MN];
vector<int> subtask1 (int n, int a, int b, int c) {
vector<int> ret(n);
int cur = 1, lst = -1;
for (int i = 0; i < n; i++) {
ret[cur-1] = (i < a ? 1 : (i < a+b ? 2 : 3));
for (int j : adj[cur]) if (j != lst) {
lst = cur; cur = j; break;
}
}
return ret;
}
vector<int> subtask2 (int n, int a, int b, int c) {
vector<int> ret(n,3);
int leaf = -1;
function<void(int)> dfs = [&] (int cur) {
bool isLeaf = 1; vis[cur] = 1;
for (int i : adj[cur]) if (!vis[i]) {
dfs(i); isLeaf = 0;
}
if (isLeaf) leaf = cur;
};
dfs(1);
assert(~leaf && leaf != 1);
ret[leaf-1] = 1;
queue<int> q; q.push(1); memset(vis,0,sizeof vis);
vis[1] = vis[leaf] = 1;
for (int i = 0; i < b; i++) {
int cur = q.front(); q.pop();
ret[cur-1] = 2;
for (int i : adj[cur]) if (!vis[i]) {
vis[i] = 1;
q.push(i);
}
}
return ret;
}
vector<int> subtask3 (int n, int a, int b, int c) {
vector<int> ret(n),sz(n+1),wot(4),par(n+1);
wot[1] = 1; wot[2] = 2; wot[3] = 3;
if (a >= b && a > c) swap(wot[1],wot[3]), swap(a,c);
else if (b >= a && b > c) swap(wot[2],wot[3]), swap(b,c);
function<void(int,int)> dfs = [&] (int cur, int p) {
sz[cur] = 1; par[cur] = p;
for (int i : adj[cur]) if (i != p) {
dfs(i,cur);
sz[cur] += sz[i];
}
};
auto bfs = [&] (int st, int dont, int num, int val) {
memset(vis,0,sizeof vis);
queue<int> q; q.push(st); vis[st] = vis[dont] = 1;
for (int i = 0; i < num; i++) {
int cur = q.front(); q.pop();
ret[cur-1] = val;
for (int j : adj[cur]) if (!vis[j]) {
vis[j] = 1;
q.push(j);
}
}
};
dfs(1,-1);
for (int i = 1; i <= n; i++) {
if (sz[i] >= a && n - sz[i] >= b) {
fill(ret.begin(),ret.end(),wot[3]);
bfs(i,par[i],a,wot[1]);
bfs(1,i,b,wot[2]);
return ret;
}
if (sz[i] >= b && n - sz[i] >= a) {
fill(ret.begin(),ret.end(),wot[3]);
bfs(i,par[i],b,wot[2]);
bfs(1,i,a,wot[1]);
return ret;
}
}
return ret;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> deg(n); int mxDeg = 0;
for (int i = 0; i < (int)p.size(); i++) {
mxDeg = max(mxDeg,++deg[p[i]]);
mxDeg = max(mxDeg,++deg[q[i]]);
adj[++p[i]].push_back(++q[i]);
adj[q[i]].push_back(p[i]);
}
if (mxDeg <= 2) return subtask1(n,a,b,c);
else if (a == 1) return subtask2(n,a,b,c);
return subtask3(n,a,b,c);
}
