#include "split.h"
#include <queue>
#include <cassert>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair <int, int> pii;
#define TRACE(x) cerr << #x << ' ' << x << endl
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define fi first
#define sec second
#define pb push_back
const int MAXN = 200100;
int n;
vector <int> v[MAXN];
vector <int> bio;
bool bfs(int start, vector <int> boje, vector <int> &ret) {
queue <int> q;
bio[start] = 1;
int cnt = 0;
q.push(start);
vector <int> pos;
while (!q.empty()) {
int cvor = q.front();
q.pop();
cnt++;
pos.pb(cvor);
if (cnt == min(boje[2], boje[3])) {
int boja = 3;
if (boje[3] > boje[2]) boja = 2;
for (auto &x : pos) ret[x] = boja;
return true;
}
for (auto &ncvor : v[cvor]) {
if (bio[ncvor]) continue;
bio[ncvor] = 1;
q.push(ncvor);
}
}
return false;
}
vector <int> solve1(vector <int> boje) {
vector <int> ret;
ret.resize(n);
REP(i, n) {
if (bio[i]) continue;
if (bfs(i, boje, ret)) {
int boja = 2;
if (boje[3] > boje[2]) boja = 3;
REP(j, n) {
if (ret[j] == 0 && boje[1]) {
ret[j] = 1;
boje[1]--;
} else if (ret[j] == 0) ret[j] = boja;
}
return ret;
}
}
return ret;
}
int sub[MAXN];
void dfs(int cvor, int par) {
sub[cvor]++;
for (auto &ncvor : v[cvor]) {
if (ncvor == par) continue;
dfs(ncvor, cvor);
sub[cvor] += sub[ncvor];
}
}
void bojaj(int cvor, int par, int boja, vector <int> &boje, vector <int> &ret) {
if (boje[boja] == 0) return;
ret[cvor] = boja;
boje[boja]--;
for (auto &ncvor : v[cvor]) {
if (par == ncvor) continue;
bojaj(ncvor, cvor, boja, boje, ret);
}
}
vector <int> rezi(int A, int B, vector <int> boje, int ka, int kb) {
vector <int> ret;
ret.resize(n);
bojaj(A, B, ka, boje, ret);
bojaj(B, A, kb, boje, ret);
REP(i, n) if (!ret[i]) ret[i] = 6 - ka - kb;
return ret;
}
vector <int> stablo(vector <int> boje) {
dfs(0, -1);
vector <pii> B;
FOR(i, 1, 4) B.pb({boje[i], i});
sort(B.begin(), B.end());
REP(i, MAXN) {
for (auto &j : v[i]) {
int x = i, y = j;
if (sub[x] > sub[y]) swap(x, y);
int ostalo = n - sub[x];
if (ostalo >= B[0].fi && sub[x] >= B[1].fi) {
return rezi(y, x, boje, B[0].sec, B[1].sec);
}
if (ostalo >= B[1].fi && sub[x] >= B[0].fi) {
return rezi(x, y, boje, B[0].sec, B[1].sec);
}
}
}
vector <int> ret;
ret.resize(n);
return ret;
}
vector <int> tmp;
void f(int cvor, int par) {
tmp.pb(cvor);
bio[cvor] = 1;
for (auto &ncvor : v[cvor]) {
if (bio[ncvor]) continue;
f(ncvor, cvor);
}
}
bool cmp(const vector <int> &a, const vector <int> &b) {
return a.size() < b.size();
}
vector <int> lanci(vector <int> boje) {
vector <pii> B;
FOR(i, 1, 4) B.pb({boje[i], i});
sort(B.begin(), B.end());
vector <vector <int> > l;
REP(i, n) {
if (!bio[i] && v[i].size() <= 1) {
tmp.clear();
f(i, -1);
l.pb(tmp);
}
}
REP(i, n) {
if (!bio[i]) {
tmp.clear();
f(i, -1);
l.pb(tmp);
}
}
sort(l.begin(), l.end(), cmp);
int tu = 0;
vector <int> ret;
ret.resize(n);
for (auto &L : l) {
if (L.size() >= B[0].fi + B[1].fi) {
REP(i, B[0].fi) ret[L[i]] = B[0].sec;
FOR(i, B[0].fi, B[0].fi + B[1].fi) ret[L[i]] = B[1].sec;
REP(i, n) if (!ret[i]) ret[i] = B[2].sec;
return ret;
}
}
int ok = 0;
REP(t, 2) {
for (auto &L : l) {
if (L.size() >= B[t].fi) {
REP(i, B[t].fi) ret[L[i]] = B[t].sec;
ok++;
break;
}
}
}
if (ok == 2) REP(i, n) if (!ret[i]) ret[i] = B[2].sec;
else {
ret.clear();
ret.resize(n);
}
return ret;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
bio.resize(n);
REP(i, p.size()) {
v[p[i]].pb(q[i]);
v[q[i]].pb(p[i]);
}
vector <int> boje = {0, a, b, c};
int deg = 0;
REP(i, n) deg = max(deg, (int)v[i].size());
if (deg <= 2) return lanci(boje);
if (p.size() == n - 1) return stablo(boje);
return solve1(boje);
}
