#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fr first
#define se second
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool seen[MAXN];
int ans[MAXN];
vector<int> adj[MAXN];
bool artpoint[MAXN];
int in[MAXN], low[MAXN];
int t = 0;
void dfsArt(int node, int dad) {
in[node] = low[node] = ++t;
seen[node] = 1;
int kids = 0;
for (auto u : adj[node]) {
if (u == dad) continue;
if (seen[u]) low[node] = min(low[node], in[u]);
else {
dfsArt(u, node);
low[node] = min(low[node], low[u]);
kids++;
if (node == 0) continue;
if (low[u] >= in[node]) artpoint[node] = 1;
}
}
if ((node == 0) && kids) artpoint[node] = 1;
}
int qtd, qual;
void dfs(int node) {
seen[node] = 1;
ans[node] = qual;
qtd--;
for (auto u : adj[node]) if (!seen[u] && (qtd > 0)) dfs(u);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<pii> ord = {{a, 1}, {b, 2}, {c, 3}};
sort(ord.begin(), ord.end());
for (int i = 0; i < ((int) p.size()); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
// calc
dfsArt(0, -1);
int start = 0;
for (int i = 0; i < n; i++) if (!artpoint[i]) start = i;
memset(seen, 0, sizeof seen);
seen[start] = 1;
ans[start] = 1;
if (start > 0) start = 0;
else start = 1;
qtd = ord[1].fr;
qual = ord[1].se;
dfs(start);
// retornar
vector<int> resposta(n);
for (int i = 0; i < n; i++) resposta[i] = ans[i];
for (auto& u : resposta) if (u == 0) u = ord[2].se;
return resposta;
}
