#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int centroid_find(int n, vector<vector<int>> (&edges))
{
//create a spanning tree
//vector<vector<int>> new_edges(n);
vector<int> parent(n, -2);
vector<int> nodes;
nodes.push_back(0);
parent[0] = -1;
int curr = 0;
int total = 1;
while (curr < total)
{
int x = nodes[curr]; curr++;
for (int y: edges[x])
{
if (parent[y] == -2)
{
parent[y] = x;
nodes.push_back(y);
total++;
//new_edges[]
}
}
}
vector<int> subtreesize(n, 1);
for (int i=n-1; i>0; i--)
{
int x = nodes[i];
subtreesize[parent[x]] += subtreesize[x];
}
//now identify the centroid
int bes = n+1;
int cap = (n+1)/2;
int centroid = -1;
for (int i=0; i<n; i++)
if ((subtreesize[i]<bes) and (subtreesize[i]>=cap))
{
bes = subtreesize[i];
centroid = i;
}
return centroid;
}
vector<int> find_split_wlog(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<vector<int>> edges(n);
int e = p.size();
for (int i=0; i<e; i++)
{
int pp = p[i];
int qq = q[i];
edges[pp].push_back(qq);
edges[qq].push_back(pp);
}
int root = centroid_find(n, edges);
//cout << root << '\n';
//step 3: perform a dfs and identify whether its possible or not
vector<int> parent(n, -2);
stack<pair<int, int>> nodes;
vector<int> push_order;
vector<vector<int>> children(n);
parent[root] = -1;
nodes.push({root, 0});
push_order.push_back(root);
while (!nodes.empty())
{
pair<int, int> info = nodes.top();
int x = info.first; int y = info.second;
nodes.pop();
if ((y+1)<edges[x].size())
nodes.push({x, y+1});
int z = edges[x][y];
if (parent[z]==-2)
{
parent[z] = x;
nodes.push({z, 0});
push_order.push_back(z);
children[x].push_back(z);
}
}
vector<int> subtreesize(n, 1);
for (int i=n-1; i>0; i--)
{
int x = push_order[i];
subtreesize[parent[x]] += subtreesize[x];
//cout << x << subtreesize[x] << '\n';
}
int node_min = n+1;
int root_a = -1;
for (int i: edges[root])
if ((i!=root) and (subtreesize[i] < node_min) and (subtreesize[i]>=a))
{
node_min = subtreesize[i];
root_a = i;
}
if (root_a == -1)
{
vector<int> ans(n, 0);
return ans;
}
//then a solution is possible
vector<int> ans(n, 3);
queue<int> group_a;
group_a.push(root_a);
ans[root_a] = 1;
int members = 1;
while (members < a)
{
int x = group_a.front(); group_a.pop();
for (int y: children[x])
if (members < a)
{
ans[y] = 1;
group_a.push(y);
members++;
}
}
queue<int> group_b;
group_b.push(root);
ans[root] = 2;
members = 1;
while (members < b)
{
int x = group_b.front(); group_b.pop();
for (int y: children[x])
if ((members < b) and (ans[y]==3))
{
ans[y] = 2;
group_b.push(y);
members++;
}
}
return ans;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> rewrite = {0, 1, 2, 3};
for (int i=0; i<5; i++)
{
if (a>b)
{
swap(a, b);
swap(rewrite[1], rewrite[2]);
}
if (b>c)
{
swap(b, c);
swap(rewrite[2], rewrite[3]);
}
}
vector<int> ans = find_split_wlog(n, a, b, c, p, q);
for (int i=0; i<n; i++)
{
ans[i] = rewrite[ans[i]];
}
return ans;
}
int main() {
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];
vector<int> result = find_split(n, a, b, c, p, q);
for (int i=0; i<(int)result.size(); i++)
printf("%s%d", ((i>0)?" ":""), result[i]);
printf("\n");
return 0;
}
