#include "split.h"
#include <cstdio>
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<bool,bool> pbb;
typedef vector<pbb> vbb;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
const ll INF=1000000001;
vi solve1(int n, int a, int b, int c, vvi conexiones){
vi res(n,0);
queue<int> cola;
cola.push(0);
vb porvisitar(n,true);
while (cola.size()){
int x=cola.front();
cola.pop();
if (porvisitar[x]){
porvisitar[x]=false;
if (b){
res[x]=2;
b--;
}
else if (c){
res[x]=3;
c--;
}
else res[x]=1;
for (int y:conexiones[x]) cola.push(y);
}
}
return res;
}
vi solve2(int n, int a, int b, int c, vvi conexiones){
int inicio=0;
for (int i=0;i<n;i++){
if (conexiones[i].size()==0) inicio=i;
}
vi res(n,0);
stack<int> cola;
cola.push(inicio);
vb porvisitar(n,true);
while (cola.size()){
int x=cola.top();
cola.pop();
if (porvisitar[x]){
porvisitar[x]=false;
if (b){
res[x]=2;
b--;
}
else if (c){
res[x]=3;
c--;
}
else res[x]=1;
for (int y:conexiones[x]) cola.push(y);
}
}
return res;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res;
vvi conexiones(n);
int m=p.size();
for (int i=0;i<m;i++){
conexiones[p[i]].push_back(q[i]);
conexiones[q[i]].push_back(p[i]);
}
if (a==1) return solve1(n,a,b,c,conexiones);
else return solve2(n,a,b,c,conexiones);
}
