#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 1e5 + 5;
int sz[N], f[N], p[N], bl[N], h[N];
vector<int> V[N], adj[N], eb[N];
vector<int> ans, b(4);
vector<pii> x;
void dfs(int u, int P) {
f[u] = 1;
p[u] = P;
h[u] = h[P] + 1;
for(int i = 0; i < V[u].size(); i++) {
if(f[V[u][i]]) {
eb[u].push_back(V[u][i]);
continue;
}
dfs(V[u][i], u);
adj[u].push_back(V[u][i]);
sz[u] += sz[V[u][i]];
}
++sz[u];
}
void dfs2(int u, int P) {
int F = 0;
for(int i = 0; i < eb[u].size();i++) {
if(h[eb[u][i]] < h[P]) {
F = 1;
x.push_back({i, sz[eb[u][i]]});
break;
}
}
if(F) return;
for(int i = 0; i < adj[u].size(); i++) {
dfs2(adj[u][i], P);
}
}
void dfs3(int u, int t) {
if(!b[t]) return;
--b[t];
ans[u] = t;
f[u] = 1;
for(int i = 0; i < adj[u].size(); i++) {
if(bl[adj[u][i]]) continue;
if(!b[t]) return;
dfs3(adj[u][i], t);
}
}
void dfs4(int u, int t) {
if(!b[t]) return;
--b[t];
ans[u] = t;
f[u] = 1;
for(int i = 0; i < V[u].size(); i++) {
if(f[V[u][i]]) continue;
if(!b[t]) return;
dfs4(V[u][i], t);
}
}
int get(vector<int> x, int t) {
pii mn;
mn = {N, 5};
for(int i = 1; i <= 3; i++) {
if(i == t) continue;
mn = min(mn, {x[i], i});
}
return mn.s;
}
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
ans.resize(n);
int a = min(A, min(B, C));
b[1] = A, b[2] = B, b[3] = C;//cout << "+" << endl;
for(int i = 0; i < p.size(); i++) {
int u = p[i], v = q[i];
V[u].push_back(v);
V[v].push_back(u);
}
dfs(0, 0);
for(int i = 0; i < n; i++) {
if(sz[i] < a) continue;
int F = 0;
for(int j = 0; j < adj[i].size(); j++) {
if(sz[adj[i][j]] >= a) {
F = 1;
break;
}
}
if(F) continue;
if(!i) return ans;
x.clear();
for(int j = 0; j < adj[i].size(); j++) {
dfs2(adj[i][j], i);
}
int oth = n - sz[i];
while(oth < a) {
if(!x.size()) break;
oth += x.back().s;
bl[x.back().f] = 1;
x.pop_back();
}
if(oth < a) return ans;
int t1 = get(b, 0), t2 = get(b, t1);
for(int j = 0; j < n; j++) f[j] = 0;
dfs3(i, (oth >= b[t2] ? t1 : t2));
dfs4(p[i], (oth < b[t2] ? t1 : t2)); assert(!b[t2]&&!b[t1]);
for(int j = 0; j < n; j++) if(!ans[j]) ans[j] = 6 - t1 - t2;
return ans;
}
return ans;
}
