#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
vector<bool> visited(MAXN, false);
vector<int> adj[MAXN];
vector<int> S(MAXN, 0);
vector<int> S_reset(MAXN, 0);
int v = 0;
void dfs(int x, int s, int id){
if(visited[x]) return;
visited[x] = true;
S[x] = id;
v++;
for(auto u : adj[x]){
if(v == s) return;
dfs(u, s, id);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
vector<int> s(n, 0);
for(int i = 0; i < n; i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
bool d = false;
dfs(0, a, 1);
if(v != a){
return s;
}
for(int i = 0; i < n; i++){
if(S[i] != 0){
s[i] = S[i];
S[i] = 0;
}
}
v = 0;
for(int i = 1; i < n; i++){
if(visited[i] == false){
dfs(i, b, 2);
if(v != b){
v = 0;
S = S_reset;
}
else{
d = true;
v = 0;
for(int i = 0; i < n; i++){
if(S[i] == 2){
s[i] = 2;
S[i] = 0;
}
}
break;
}
}
}
if(d == false){
for(int i = 0; i < n; i++){
s[i] = 0;
}
return s;
}
for(int i = 0; i < n; i++){
if(s[i] == 0) s[i] = 3;
}
return s;
}
