#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector<vector<unsigned>> g;
vector<unsigned> preoder, postorder, subtree_size;
vector<bool> has_backward_edge;
bool is_in_subtree(unsigned u, unsigned v)
{
return preoder[u] < preoder[v] && postorder[u] > postorder[v];
}
pair<unsigned, unsigned> traverse(
unsigned u, vector<bool> &visited, unsigned i = 0, unsigned j = 0)
{
preoder[u] = i++;
visited[u] = 1;
subtree_size[u] = 1;
for (unsigned const &v : g[u])
if (!visited[v])
{
tie(i, j) = traverse(v, visited, i, j);
subtree_size[u] += subtree_size[v];
}
postorder[u] = j++;
return {i, j};
}
void find_backward_edges(unsigned u, vector<bool> &visited)
{
visited[u] = 1;
for (unsigned const &v : g[u])
{
if (!visited[v])
find_backward_edges(v, visited);
else if (!is_in_subtree(u, v))
has_backward_edge[u] = 1;
}
}
unsigned find_split_node(unsigned u, vector<bool> &visited, unsigned a)
{
visited[u] = 1;
unsigned curr_size = subtree_size[u];
bool is_min_greater = 1;
for (unsigned const &v : g[u])
if (!visited[v] && subtree_size[v] >= a)
is_min_greater = 0;
if (is_min_greater)
for (unsigned const &v : g[u])
{
if (!visited[v])
{
if (curr_size - subtree_size[v] < a)
return u;
if (has_backward_edge[v])
curr_size -= subtree_size[v];
}
}
for (unsigned const &v : g[u])
{
if (!visited[v])
{
unsigned x = find_split_node(v, visited, a);
if (x != UINT_MAX)
return x;
}
}
return UINT_MAX;
}
unsigned dfs_down(
unsigned u, vector<bool> &visited, vector<int> &ans, unsigned to_add,
unsigned added_size, unsigned z1, unsigned z2)
{
visited[u] = 1;
if (added_size < to_add)
{
ans[u] = z1;
added_size++;
}
else
ans[u] = z2;
for (unsigned const &v : g[u])
{
if (!visited[v] && is_in_subtree(u, v))
added_size = dfs_down(v, visited, ans, to_add, added_size, z1, z2);
}
return added_size;
}
unsigned dfs_up(
unsigned u, vector<bool> &visited, vector<int> &ans, unsigned to_add,
unsigned added_size, unsigned z1, unsigned z2)
{
visited[u] = 1;
if (added_size < to_add)
{
ans[u] = z1;
added_size++;
}
else
ans[u] = z2;
for (unsigned const &v : g[u])
{
if (!visited[v])
added_size = dfs_up(v, visited, ans, to_add, added_size, z1, z2);
}
return added_size;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
array<pair<unsigned, unsigned>, 3> y;
y[0] = {a, 1}, y[1] = {b, 2}, y[2] = {c, 3};
sort(y.begin(), y.end());
g = vector<vector<unsigned>>(n);
preoder = vector<unsigned>(n);
postorder = vector<unsigned>(n);
subtree_size = vector<unsigned>(n);
for (size_t i = 0; i < p.size(); i++)
{
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
vector<bool> visited(n, 0);
traverse(0, visited);
fill(visited.begin(), visited.end(), 0);
has_backward_edge = vector<bool>(n, 0);
find_backward_edges(0, visited);
fill(visited.begin(), visited.end(), 0);
unsigned x = find_split_node(0, visited, y[0].first);
if (x == UINT_MAX)
return vector<int>(n, 0);
else
{
fill(visited.begin(), visited.end(), 0);
unsigned p = UINT_MAX;
for (unsigned const &v : g[x])
if (!is_in_subtree(x, v))
{
p = v;
break;
}
vector<int> ans(n);
dfs_down(x, visited, ans, subtree_size[x] >= y[1].first ? y[1].first : y[0].first, 0,
subtree_size[x] >= y[1].first ? y[1].second : y[0].second,
y[2].second);
dfs_up(p, visited, ans, subtree_size[x] >= y[1].first ? y[0].first : y[1].first, 0,
subtree_size[x] >= y[1].first ? y[0].second : y[1].second,
y[2].second);
return ans;
}
}
