#include <bits/stdc++.h>
#include "split.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define pb push_back
#define ff first
#define ss second
const int nax = 1e5 + 4;
int n, m, a, b, c;
vi adj[nax];
vi ans;
int d[nax], sz[nax];
bool ok = false;
int head1, id1;
int head2, id2;
int id3;
int card[4];
void dfs(int x, int p = 0)
{
sz[x] = 1;
d[x] = d[p] + 1;
for(auto e: adj[x])
{
if(e != p)
{
dfs(e, x);
sz[x] += sz[e];
}
}
if(ok)
return;
if(sz[x] >= a && n - sz[x] >= b)
{
ok = true;
head1 = x, id1 = 1;
head2 = p, id2 = 2;
id3 = 3;
}
else if(sz[x] >= b && n - sz[x] >= a)
{
ok = true;
head1 = x, id1 = 2;
head2 = p, id2 = 1;
id3 = 3;
}
else if(sz[x] >= a && n - sz[x] >= c)
{
ok = true;
head1 = x, id1 = 1;
head2 = p, id2 = 3;
id3 = 2;
}
else if(sz[x] >= c && n - sz[x] >= a)
{
ok = true;
head1 = x, id1 = 3;
head2 = p, id2 = 1;
id3 = 2;
}
else if(sz[x] >= b && n - sz[x] >= c)
{
ok = true;
head1 = x, id1 = 2;
head2 = p, id2 = 3;
id3 = 1;
}
else if(sz[x] >= c && n - sz[x] >= b)
{
ok = true;
head1 = x, id1 = 3;
head2 = p, id2 = 3;
id3 = 1;
}
}
int curid = 0;
int cnt = 0;
void dfs2(int x, int p)
{
ans[x] = curid;
cnt++;
for(auto e: adj[x])
{
if(cnt == card[curid])
return;
if(e != p)
{
dfs2(e, x);
}
}
}
vi find_split(int N, int A, int B, int C, vi P, vi Q)
{
n = N, a = A, b = B, c = C;
m = P.size();
for(int i =0 ; i < n; i++)
adj[i].clear();
card[1] = a, card[2] = b, card[3] = c;
for(int i = 0; i < m; i ++)
{
adj[P[i]].pb(Q[i]);
adj[Q[i]].pb(P[i]);
}
ans.assign(n, 0);
d[0] = -1;
dfs(0, 0);
if(!ok)
return ans;
curid = id1;
dfs2(head1, head2);
curid = id2;
cnt = 0;
dfs2(head2, head1);
for(int i = 0 ; i < n ; i++)
{
if(ans[i] == 0)
ans[i] = id3;
}
return ans;
}
/*
int32_t main()
{
int N, M, A, B, C;
cin >> N >> M >> A >> B >> C;
vi P(M), Q(M);
for(int i = 0; i < M; i++)
cin >> P[i] >> Q[i];
vi ANS = find_split(N, A, B, C, P, Q);
for(auto e: ANS)
cout << e << ' ';
}
*/
