#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vint vector<int>
#define vll vector<long long>
#define fo(a, b, c) for (int a = b; a < (int)c; a++)
#define rfo(a, b, c) for (int a = b - 1; a >= (int)c; a--)
#define print(x) cout << x << "\n"
vint subtask1(int n, int a, int b, int c, vll roads[])
{
vint ans;
ans.resize(n);
int count = 0;
int prev = -1;
int on = 0;
int setOn = 0;
vint lims;
lims.push_back(a);
lims.push_back(b);
lims.push_back(c);
fo(i,0,n){
if(roads[i].size()==1){
on=i;
break;
}
}
do
{
count++;
ans[on] = setOn + 1;
if (count == lims[setOn])
{
setOn++;
count = 0;
}
for (auto x : roads[on])
{
if (x != prev)
{
prev = on;
on = x;
break;
}
}
} while (setOn != 3);
return ans;
}
vint subtask2(int n, int a, int b, int c, vll roads[])
{
vint ans;
int limit = 0, changeto = 0;
if (b > c) // run through C
{
ans.assign(n, 2);
limit = c;
changeto = 3;
}
else
{
ans.assign(n, 3);
limit = b;
changeto = 2;
}
//find b nodes connected, then change a random different node to a, let the rest be c
set<int> visited;
deque<int> toVisit; // node to visit
toVisit.push_back(0);
int on = -1;
int prev = -1;
while (visited.size() < limit)
{
while (toVisit.size() > 0)
{
prev = on;
on = toVisit.back();
toVisit.pop_back();
visited.insert(on);
ans[on] = changeto;
break;
}
for (auto x : roads[on])
{
if (x != prev && visited.count(x) == 0)
{
toVisit.push_back(x);
}
}
}
ans[toVisit.back()] = 1;
return ans;
}
// n - number of attractions
// a, b, c - size of sets a, b, c
// p, q - length m arrays containing the starts and stops of all the roads
//return an array of length n, all zeros if not possible, otherwise 1, 2 or 3 in each space
vint find_split(int n, int a, int b, int c, vint p, vint q)
{
vint ans;
vll roads[n];
fo(i, 0, p.size())
{
roads[p[i]].push_back(q[i]);
roads[q[i]].push_back(p[i]);
}
if (a == 1)
{
ans = subtask2(n, a, b, c, roads);
}
else
{
ans = subtask1(n, a, b, c, roads);
}
return ans;
}
