// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
using namespace std;
vector<vector<int> > adj;
vector<int> pr, sub;
vector<array<int, 2> > ord(3);
vector<int> ans;
int m, N;
vector<int> spl(2, -1);
void dfs(int node, int par) {
pr[node] = par;
sub[node] = 1;
for(auto c : adj[node]) {
if(c == pr[node]) continue;
dfs(c, node);
sub[node] += sub[c];
}
vector<int> szs = {N - sub[node], sub[node]};
bool swa = 0;
if(szs[0] > szs[1]) {
swa = 1;
swap(szs[0], szs[1]);
}
if(szs[0] > ord[0][0] && szs[1] > ord[1][0]) {
spl[0] = 0; spl[1] = node;
if(swa) swap(spl[0], spl[1]);
}
}
int cnt = 0;
void dfs2(int node, int forb, int num) {
if(node == forb || cnt == ord[num][0]) return;
cnt++;
ans[node] = ord[num][1];
for(auto c : adj[node]) {
if(c == pr[node]) continue;
dfs2(c, forb, num);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
adj.assign(n, vector<int>());
ans.assign(n, 0);
sub.assign(n, 0);
spl.assign(2, -1);
ord.resize(3);
ord[0] = {a, 1};
ord[1] = {b, 2};
ord[2] = {c, 3};
sort(all(ord));
N = n;
pr.assign(n, 0);
m = (int)p.size();
for(int i = 0; i < m; i++) {
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
dfs(0, 0);
if(spl[0] == -1) {
return ans;
}
cnt = 0;
dfs2(spl[0], spl[1], 0);
cnt = 0;
dfs2(spl[1], -1, 1);
REP(i, n) {
if(ans[i] == 0) ans[i] = ord[2][1];
}
return ans;
}
