#include "split.h"
//#include "grader.cpp"
#include <set>
#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
vector <int> graph[MAXN];
vector <vector <int>> solve1(int a, int b, int c)
{
vector <int> order;
vector <bool> used;
used.assign(n+5, false);
function <void(int)> dfs = [&](int x)
{
order.push_back(x);
//cout << x << " ";
used[x] = true;
for(int y: graph[x])
{
if(used[y]==false) dfs(y);
}
};
//cout << '\n';
dfs(0);
vector <vector <int>> out;
out.push_back({});
for(int i = 0;i<a;i++) out.back().push_back(order[i]);
out.push_back({});
for(int i = a;i<a+b;i++) out.back().push_back(order[i]);
out.push_back({});
for(int i = a+b;i<a+b+c;i++) out.back().push_back(order[i]);
return out;
}
int recogniseSubtask(int a, int b, int c)
{
int maxDeg = 0;
for(int x = 0;x<n;x++)
{
maxDeg = max(maxDeg, int(graph[x].size()));
}
if(maxDeg<=2) return 1;
if(a==1) return 2;
if(m==n-1) return 3;
}
int depth[MAXN], treeSize[MAXN];
void DFSInit(int x, int last, int level)
{
treeSize[x] = 1;
depth[x] = level;
for(int y: graph[x])
{
if(y==last) continue;
DFSInit(y, x, level+1);
treeSize[x] += treeSize[y];
}
}
int largestKid[MAXN];
multiset <pair <int, int>> ms[MAXN];
int rootPos[MAXN];
void DFSFind(int x, int last, bool &found, int a, int b, int c)
{
//cout << x << " ---- " << treeSize[x] << '\n';
if(found==true) return;
if(graph[x].size()==1)
{
largestKid[x] = x;
ms[x] = {make_pair(1, x)};
}
largestKid[x] = -1;
for(int y: graph[x])
{
if(y==last) continue;
DFSFind(y, x, found, a, b, c);
if(found==true) return;
if(largestKid[x]==-1 || ms[ largestKid[y] ].size()>ms[ largestKid[x] ].size())
{
largestKid[x] = largestKid[y];
}
}
for(int y: graph[x])
{
if(y==last) continue;
if(largestKid[y]==largestKid[x]) continue;
for(pair <int, int> item: ms[ largestKid[y] ])
ms[ largestKid[x] ].insert(item);
}
ms[ largestKid[x] ].insert({treeSize[x], x});
if(treeSize[x]>=a+b && x==0)
{
auto it = ms[ largestKid[x] ].lower_bound(make_pair(b, -1));
if(it!=ms[ largestKid[x] ].end() && treeSize[x]-it->first>=a)
{
//cout << "found at " << x << '\n';
found = true;
rootPos[x] = 1;//a
rootPos[it->second] = 2;//b
}
}
}
vector <vector <int>> solve3(int a, int b, int c)
{
for(int x = 0;x<n;x++)
{
rootPos[x] = 0;
ms[x].clear();
depth[x] = 0;
treeSize[x] = 0;
}
DFSInit(0, -1, 1);
bool found = false;
DFSFind(0, -1, found, a, b, c);
if(found==false) return {};
vector <vector <int>> out;
function <void(int, int, int, vector <int>&, int)> DFSMark = [&](int x, int last, int col, vector <int> &v, int goal)
{
if(v.size()==goal) return;
//cout << x << " with col: " << col << '\n';
rootPos[x] = col;
v.push_back(x);
for(int y: graph[x])
{
if(y==last) continue;
if(rootPos[y]!=0) continue;
DFSMark(y, x, col, v, goal);
}
};
for(int x = 0;x<n;x++)
{
if(rootPos[x]==1)
{
out.push_back({});
DFSMark(x, -1, rootPos[x], out.back(), a);
break;
}
}
for(int x = 0;x<n;x++)
{
if(rootPos[x]==2)
{
out.push_back({});
DFSMark(x, -1, rootPos[x], out.back(), b);
break;
}
}
out.push_back({});
for(int x = 0;x<n;x++)
{
if(rootPos[x]==0)
{
out.back().push_back(x);
}
}
return out;
}
vector <int> getOutput(vector <vector <int>> v, int a, int b, int c)
{
if(v.size()==0)
{
vector <int> out;
out.assign(n, 0);
return out;
}
if(v[1].size()==a) swap(v[0], v[1]);
if(v[2].size()==a) swap(v[0], v[2]);
if(v[2].size()==b) swap(v[1], v[2]);
vector <int> out;
out.resize(a+b+c);
for(int x: v[0]) out[x] = 1;
for(int x: v[1]) out[x] = 2;
for(int x: v[2]) out[x] = 3;
return out;
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q)
{
n = _n;
m = p.size();
for(int i = 0;i<m;i++)
{
graph[ p[i] ].push_back(q[i]);
graph[ q[i] ].push_back(p[i]);
}
int subtask = recogniseSubtask(a, b, c);
vector <vector <int>> rawOutput;
if(subtask==1)
{
rawOutput = solve1(a, b, c);
return getOutput(rawOutput, a, b, c);
}
if(subtask==2)
{
rawOutput = solve1(b, c, a);
return getOutput(rawOutput, a, b, c);
}
if(subtask==3)
{
//cout << "subtask 3" << '\n';
vector <int> sizes = {a, b, c};
sort(sizes.begin(), sizes.end());
do
{
rawOutput = solve3(sizes[0], sizes[1], sizes[2]);
if(rawOutput.size()!=0) break;
}
while(next_permutation(sizes.begin(), sizes.end()));
return getOutput(rawOutput, a, b, c);
}
}
/*
5 5
1 2 2
0 1
1 2
2 3
3 4
4 0
5 4
2 2 2
0 1
0 2
0 3
0 4
8 7
2 2 4
0 1
0 2
0 5
0 6
0 7
1 3
2 4
*/
