#include <bits/stdc++.h>
#include "split.h"
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
struct DisjointSet {
vector<int> par, Sz;
void init(int n) { par.resize(n + 5); Sz.resize(n + 5);
REP(i, n) par[i] = i, Sz[i] = 1;}
int get(int u) { return (par[u] == u ? u : par[u] = get(par[u])); }
bool merge(int u, int v) {
u = get(u); v = get(v);
if(u == v) return false;
if(Sz[u] < Sz[v]) swap(u, v);
par[v] = u; Sz[u] += Sz[v];
return true;
}
};
bool subtaks1(vector<int> p, vector<int> q, int n) {
vector<int> cnt(n); REP(i, (int)q.size()) { cnt[p[i]]++; cnt[q[i]]++; }
REP(i, n) if(cnt[i] >= 3) return false;
return true;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res(n); if(subtaks1(p, q, n)) {
DisjointSet dsu; dsu.init(n); vector<vector<int>> g; g.resize(n + 5);
REP(i, (int)p.size()) if(dsu.merge(p[i], q[i])) {
g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]);
} vector<int> h(n);
function<void(int, int)> DFS = [&](int u, int p) {
FORE(it, g[u]) if((*it) != p) {
h[(*it)] = h[u] + 1; DFS(*it, u);
}
};
DFS(0, -1);
int newRoot = 0; FOR(i, 1, n - 1) if(h[i] > h[newRoot]) newRoot = i;
vector<int> child(n);
function<void(int, int)> DFS_Child = [&](int u, int p) {
int next_v = -1;
FORE(it, g[u]) if((*it) != p) { next_v = (*it); break; }
if(next_v != -1) {
child[u] = next_v; DFS_Child(child[u], u);
}
};
DFS_Child(newRoot, -1); int cur_cnt = 0;
while(cur_cnt < a) {
cur_cnt++; res[newRoot] = 1; newRoot = child[newRoot];
}
cur_cnt = 0;
while(cur_cnt < b) {
cur_cnt++; res[newRoot] = 2; newRoot = child[newRoot];
}
REP(i, n) if(res[i] == 0) res[i] = 3;
} else if(a == 1) {
// set all 2
DisjointSet dsu; dsu.init(n); vector<pair<int, char>> cmp_list = {{a, 1}, {b, 2}, {c, 3}};
sort(ALL(cmp_list));
vector<vector<int>> g; g.resize(n + 5);
REP(i, (int)p.size()) {
g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]);
dsu.merge(p[i], q[i]);
}
bool _check = false; int idx = -1;
REP(i, n) if(dsu.Sz[dsu.get(i)] >= cmp_list[1].first) { _check = true; idx = i; break; }
if(_check == false) return res;
int cnt = 0; vector<bool> check(n); check[idx] = true;
function<void(int)> DFS = [&](int u) {
if(cnt == cmp_list[1].first) return;
FORE(it, g[u]) if(!check[*it]) {
res[*it] = cmp_list[1].second; cnt++; check[*it] = true;
if(cnt == cmp_list[1].first) return;
DFS(*it);
}
}; DFS(idx); REP(i, n) if(res[i] != cmp_list[1].second) { res[i] = cmp_list[0].second; break; }
REP(i, n) if(res[i] == 0) res[i] = cmp_list[2].second;
}
return res;
}
