#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 7;
vector < int > graph[N] , color;
int cur_color = 1;
int dfs(int node , int sayac){
if(sayac == 0)return node;
// cout << "dfs : " << node << " , " << cur_color << endl;
color[node] = cur_color;
int ret = -1;
for(auto itr : graph[node]){
if(color[itr] == -1){
ret = dfs(itr , sayac - 1);
break;
}
}
return ret;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
color.assign(n , -1);
for(int i = 0;i<sz(p);i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
bool bl = 1;
for(int i = 0;i<n;i++){
bl &= sz(graph[i]) <= 2;
}
if(bl){
int root = 0;
for(int i = 0;i<n;i++){
if(sz(graph[i]) == 1){
root = i;
break;
}
}
// cout << "root0 : " << root << endl;
root = dfs(root , a);
cur_color++;
// cout << "root1 : " << root << endl;
root = dfs(root , b);
cur_color++;
// cout << "root2 : " << root << endl;
root = dfs(root , c);
}
return color;
}
