/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const char nl = '\n';
int tutu;
const int N = 2e5+10;
vector<int> g[N];
vector<pair<int, int>> arr;
int tin[N], tout[N];
int ss[N], cut[N];
int vis[N];
void dfs(int a, int p) {
tin[a] = tout[a] = tutu++;
ss[a] = 1;
//vis[a] = 1;
for (auto i: g[a]) {
if (i == p)continue;
if (!tin[i]) {
dfs(i, a);
ss[a] += ss[i];
tout[a] = min(tout[a], tout[i]);
continue;
}
tout[a] = min(tout[a], tin[i]);
}
}
int centroid(int u, int p) {
for (auto i: g[u])if (ss[i] >= arr[0].first && i != p)return centroid(i, u);
return u;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
tutu = 1; int m = sz(p);
for (int i = 0; i < m; ++i) {
g[q[i]].push_back(p[i]);
g[p[i]].push_back(q[i]);
}
arr.push_back({a, 1});
arr.push_back({b, 2});
arr.push_back({c, 3});
sort(all(arr));
vector<int> ans(n, arr[2].second);
function<void(int)> color_1 = [&](int u)
{
if (arr[1].first)ans[u] = arr[1].second, --arr[1].first;
else return;
vis[u] = 1;
for (auto i: g[u])color_1(i);
};
function<void(int)> color_0 = [&](int u)
{
if (arr[0].first)ans[u] = arr[0].second, --arr[0].first;
vis[u] = 1;
for (auto i: g[u])if (!vis[i])color_0(i);
};
dfs(0, 0);
int fnd = centroid(0, 0);
//cout << fnd << nl;
for (auto i: g[fnd]) {
if (ss[i] >= arr[0].first)continue; // parent
if (tout[i] < tin[fnd]) { // back edge
if (ss[fnd]-ss[i] >= arr[0].first)ss[fnd] -= ss[i], cut[i] = 1;
}
}
if(n - ss[fnd] >= arr[1].first) swap(arr[0], arr[1]);
if(n - ss[fnd] >= arr[0].first) {
--arr[1].first;
vis[fnd] = 1;
ans[fnd] = arr[1].second;
for (auto i: g[fnd])if (!cut[i])color_1(i);
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
color_0(i);
break;
}
}
} else return vector<int>(n, 0);
return ans;
}
//void solve() {
//int n, m; cin >> n >> m;
//int a, b, c;
//cin >> a >> b >> c;
//vector<int> u(m), v(m);
//for (int i = 0; i < m; ++i)cin >> u[i] >> v[i];
//vector<int> ans = find_split(n, a, b, c, u, v);
//for (auto i: ans)cout << i << " ";
//}
//int32_t main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
//int t = 1;
//for (int _ = 0; _ < t; ++_) {
//solve();
//}
//return 0;
//}
