#include <bits/stdc++.h>
#include "split.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
vector<int> g[N];
int A[3], B[3], sub[N], n, Max[4], have[4];
vector<int> result, bad;
void dfs(int v, int x){
if(have[B[x]] >= Max[B[x]])
return;
result[v] = B[x];
have[B[x]] ++;
for(int u : g[v])
if(!result[u])
dfs(u, x);
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size();
n = N;
for(int i = 0; i < m; i ++){
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
A[0] = a, B[0] = 1, Max[1] = a;
A[1] = b, B[1] = 2, Max[2] = b;
A[2] = c, B[2] = 3, Max[3] = c;
if(A[2] < A[1]){
swap(A[2], A[1]);
swap(B[2], B[1]);
}
if(A[2] < A[0]){
swap(A[2], A[0]);
swap(B[2], B[0]);
}
if(A[0] < A[1]){
swap(A[0], A[1]);
swap(B[0], B[1]);
}
// for(int i = 0; i < 3; i ++)
// cout << A[i] << " " << B[i] << endl;
// for(int i = 1; i <= 3; i ++)
// cout << i << " : " << Max[i] << endl;
result.resize(n);
bad.resize(n);
dfs(0, 0);
for(int i = 0; i < n; i ++){
if(!result[i]){
dfs(i, 1);
break;
}
}
for(int i = 0; i < n; i ++)
if(!result[i])
result[i] = B[2], have[B[2]] ++;
if(have[1] != Max[1] || have[2] != Max[2] || have[3] != Max[3])
return bad;
return result;
}
