#include "split.h"
using namespace std;
vector<bool> visited;
vector<vector<int>> adj_list;
int left;
void dfs_sub_2(int i){
if(visited[i]) return;
visited[i] = true;
left--;
for(int j : adj_list[i]){
if(left > 0){
dfs_sub_2(j);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<int> res(n, 0);
adj_list.assign(n, vector<int>());
for(int i = 0; i < (int)p.size(); i++){
int a = p[i];
int b = q[i];
adj_list[a].push_back(b);
adj_list[b].push_back(a);
}
if(a == 1){
visited.assign(n, false);
left = b;
dfs_sub_2(0);
for(int i = 0; i < n; i++){
if(visited[i]){
res[i] = 2;
}
else res[i] = 3;
}
for(int i = 0; i < n; i++){
if(res[i] == 3){
res[i] = 1;
break;
}
}
}
return res;
}
