#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m, a, b, c, num[N], low[N], sz[N], timer, mid = -1, ans[N], cnt[4]; vector<int> ad[N], child[N]; vector<array<int, 2>> vt; void dfs(int u, int p = -1){ num[u] = low[u] = ++timer; sz[u] = 1; for(auto v : ad[u]) if(v != p){ if(num[v]) low[u] = min(low[u], num[v]); else{ dfs(v, u); sz[u] += sz[v]; low[u] = min(low[u], low[v]); child[u].push_back(v); } } int inSz = sz[u], outSz = n - sz[u]; for(auto v : child[u]){ if(outSz >= vt[0][0]) break; if(low[v] < num[u] && inSz - sz[v] >= vt[0][0]){ inSz -= sz[v]; outSz += sz[v]; } } if(inSz >= vt[0][0] && outSz >= vt[0][0]) mid = u; } void color(int u, int c){ if(cnt[c]){ cnt[c] -= 1; ans[u] = c; } if(!cnt[c]) return; for(auto v : child[u]){ color(v, c); } } void color2(int u, int c){ if(cnt[c]){ cnt[c] -= 1; ans[u] = c; } if(!cnt[c]) return; for(auto v : ad[u]) if(!ans[v]){ color2(v, c); } } vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q){ n = _n; a = _a; b = _b, c = _c; m = _p.size(); vt = {{a, 1}, {b, 2}, {c, 3}}; sort(vt.begin(), vt.end()); for(int i = 0; i < m; ++i){ ad[_p[i]].push_back(_q[i]); ad[_q[i]].push_back(_p[i]); } dfs(0, -1); if(mid == -1){ vector<int> res(n, 0); return res; } vector<int> p; int inSz = sz[mid], outSz = n - inSz; for(auto v : child[mid]){ if(outSz >= vt[0][0]){ p.push_back(v); continue; } if(low[v] < num[mid] && inSz - sz[v] >= vt[0][0]){ inSz -= sz[v]; outSz += sz[v]; }else p.push_back(v); } if(inSz < outSz){ cnt[vt[0][1]] = vt[0][0] - 1; ans[mid] = vt[0][1]; cnt[vt[1][1]] = vt[1][0]; for(auto v : p) color(v, vt[0][1]); color2(0, vt[1][1]); }else{ cnt[vt[1][1]] = vt[1][0] - 1; ans[mid] = vt[1][1]; cnt[vt[0][1]] = vt[0][0]; for(auto v : p) color(v, vt[1][1]); color2(0, vt[0][1]); } for(int i = 0; i < n; ++i) if(!ans[i]) ans[i] = vt[2][1]; vector<int> res; for(int i = 0; i < n; ++i) res.push_back(ans[i]); return res; } #ifdef znatsumi int32_t main(){ cin.tie(0)->sync_with_stdio(0); #define task "test" if(fopen(task ".inp", "r")){ freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } int _n, _m, _a, _b, _c; cin >> _n >> _m >> _a >> _b >> _c; vector<int> _p(_m), _q(_m); for(int i = 0; i < _m; ++i) cin >> _p[i] >> _q[i]; auto res = find_split(_n, _a, _b, _c, _p, _q); for(auto x : res) cout << x << " "; return 0; } #endif