#include <bits/stdc++.h>
//#include "split.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int ans, n, A, B, label[NMAX], cnt;
int dfsn[NMAX], low[NMAX], sz[NMAX], t;
vector<int> adj[NMAX];
void color(int x, int c){
if(label[x] != -1) return;
label[x] = (cnt-- > 0 ? c : 2);
for(int& nx : adj[x])
if(dfsn[nx] > dfsn[x]) color(nx, c);
return;
}
void dfs(int x, int p){
vector<int> C;
dfsn[x] = low[x] = ++t;
sz[x] = 1;
int mx = 0;
for(int& nx : adj[x])
if(nx != p) {
if(!dfsn[nx]){
dfs(nx, x);
low[x] = min(low[x], low[nx]);
sz[x] += sz[nx];
C.emplace_back(nx);
mx = max(mx, sz[nx]);
}
else low[x] = min(low[x], dfsn[nx]);
}
if(!ans && sz[x] >= A && mx < A){
int d = sz[x], u = n - d;
label[x] = 0;
cnt = A - 1;
for(int& nx : C){
if(d - sz[nx] >= A && low[nx] > dfsn[x]) u += sz[nx], d -= sz[nx];
else color(nx, 0);
}
ans = (u >= A ? 1 : -1);
}
return;
}
vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q) {
n = n_;
vector<pair<int, int>> arr = {{a, 1}, {b, 2}, {c, 3}};
sort(all(arr));
A = arr[0].first;
B = arr[1].first;
vector<int> res(n, 0);
for(int i = 0; i < p.size(); i++){
adj[p[i]].emplace_back(q[i]);
adj[q[i]].emplace_back(p[i]);
}
memset(label, -1, sizeof(label));
dfs(0, -1);
if(ans == -1) return res;
cnt = B;
color(0, 1);
for(int i = 0; i < n; i++) res[i] = arr[label[i]].second;
return res;
}
/*
int main(void){
int n, m, a, b, c;
cin >> n >> a >> b >> c;
cin >> m;
vector<int> p(m), q(m);
for(int i = 0; i < m; i++) cin >> p[i] >> q[i];
auto v = find_split(n, a, b, c, p, q);
for(int& x : v) cout << x << ' ';
return 0;
}
*/
