#include <bits/stdc++.h>
#include "split.h"
using namespace std;
using ll = int;
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
// Subtask 2: a = 1
// subset A is guaranteed to be connected, since it only has 1 attraction
ll M = p.size();
vector<vector<ll> > adjList(N);
for (ll i = 0; i < M; i++) {
adjList[p[i]].push_back(q[i]);
adjList[q[i]].push_back(p[i]);
}
// first, create an arbitrary subset B that is connected
set<ll> B;
queue<ll> bfs;
bfs.push(0);
B.insert(0);
while (!bfs.empty() && B.size() < b) {
ll u = bfs.front();
bfs.pop();
bool alreadyHasB = false;
for (auto &v: adjList[u]) {
if (B.find(v) == B.end()) {
bfs.push(v);
B.insert(v);
if (B.size() == b) {
alreadyHasB = true;
break;
}
}
}
if (alreadyHasB) break;
}
vector<ll> response(N, 0);
for (auto &l: B) {
response[l] = 2;
}
// make an arbitrary A, then an arbitrary C
bool flag = false;
for (ll i = 0; i < N; i++) {
if (response[i] == 0 && !flag) {
response[i] = 1;
flag = true;
} else {
response[i] = 3;
}
}
return response;
}
