#include "split.h"
#include <bits/stdc++.h>
#define int long long
#define inf ((int)1e18)
const int N = 100000;
using namespace std;
vector<int32_t> find_split(int32_t n, int32_t a, int32_t b, int32_t c, vector<int32_t> p, vector<int32_t> q) {
vector <int32_t> sub(n), ans(n);
vector <vector<int> > adj(n);
int m = p.size();
vector <pair<int, int> > fuck = {{a, 1}, {b, 2}, {c, 3}};
for(int i = 0; i < m; i++) {
int a = p[i], b = q[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
int size = 0;
auto taguntil = [&](int node, int ata, int tag, auto&& dfs) -> void {
size--;
ans[node] = tag;
for(auto it:adj[node]) {
if(it == ata) continue;
if(size) dfs(it, node, tag, dfs);
}
};
auto dfs = [&](int node, int ata, auto&& dfs) -> bool {
// cout << node << " " << ata << endl;
sub[node] = 1;
for(auto it:adj[node]) {
if(it == ata) continue;
if(dfs(it, node, dfs)) {
return true;
}
sub[node] += sub[it];
}
if(sub[node] == fuck[0].first) {
size = fuck[0].first;
taguntil(node, ata, fuck[0].second, taguntil);
size = fuck[1].first;
taguntil(ata, node, fuck[1].second, taguntil);
for(auto &it:ans) if(it == 0) it = fuck[2].second;
return true;
}
if(n - sub[node] == fuck[0].first) {
size = fuck[0].first;
taguntil(ata, node, fuck[0].second, taguntil);
size = fuck[1].first;
taguntil(node, ata, fuck[1].second, taguntil);
for(auto &it:ans) if(it == 0) it = fuck[2].second;
return true;
}
return false;
};
if(dfs(0, 0, dfs)) return ans;
swap(fuck[0], fuck[1]);
if(dfs(0, 0, dfs)) return ans;
swap(fuck[0], fuck[2]);
if(dfs(0, 0, dfs)) return ans;
return ans;
}
