#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++)
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, n) { 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) {
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;
vector<int> res(n); 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;
return res;
}
