#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MAX_N = 1e5 + 5;
int N, M, A, B, C;
vector <int> graph[MAX_N];
vector <int> res;
void dfs(int u, int p, int a) {
A--;
res[u] = a;
if(A == 0) {
swap(A, B);
a = 2;
}
for(auto v : graph[u]) {
if(res[v] == p and A > 0) {
dfs(v, p, a);
}
}
}
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) {
N = n, M = p.size(), A = a, B = b, C = c;
res.resize(N, 0);
vector <int> tmp({A, B, C});
sort(tmp.begin(), tmp.end());
A = tmp[0], B = tmp[1], C = tmp[2];
for(int i = 0; i < M; i++) {
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
int rt = 0;
for(int i = 0; i < N; i++) {
if(graph[i].size() == 1) {
rt = i;
break;
}
}
dfs(rt, 0, 1);
// for(int i = 0; i < N; i++) {
// if(res[i] == 0) {
// A = B;
// dfs(i, 0, -1);
// if(A == 0) {
// A = B, B = 0;
// dfs(i, -1, 2);
// break;
// }
// }
// }
// for(int i = 0; i < N; i++) {
// if(res[i] != 1 and res[i] != 2) {
// res[i] = 3;
// C--;
// }
// }
// if(A != 0 or B != 0 or C != 0) {
// fill(res.begin(), res.end(), 0);
// }
return res;
}
