#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 300000;
vector<uint32_t> g[N], scc[N], cycle;
unordered_map<uint32_t, vector<uint32_t>> edges[N];
set<uint32_t> keys[N];
bitset<N> visited, in_dfs_path, is_leaf;
uint32_t scc_index[N];
uint32_t dfs(size_t u)
{
if (in_dfs_path[u]) // SCC found
return u;
visited[u] = 1;
in_dfs_path[u] = 1;
while (!g[u].empty())
{
uint32_t v = scc_index[g[u][0]];
swap(g[u][0], g[u].back());
g[u].pop_back();
uint32_t x = dfs(v);
if (x != UINT32_MAX)
{
cycle.push_back(u);
if (x == u) // backtracked until the start of the cycle
{
uint32_t main = u;
for (auto const &w : cycle)
if (scc[w].size() > scc[main].size())
main = w;
in_dfs_path[u] = 0;
in_dfs_path[main] = 1;
u = main;
cycle.erase(find(cycle.begin(), cycle.end(), main));
for (auto const &w : cycle)
{
scc[u].insert(scc[u].end(), scc[w].begin(), scc[w].end());
for (auto const &y : scc[w])
scc_index[y] = u;
scc[w].clear();
is_leaf[u] = is_leaf[u] && is_leaf[w];
keys[u].insert(keys[w].begin(), keys[w].end());
for (auto const &c : keys[w])
{
auto it = edges[u].find(c);
if (it != edges[u].end())
{
g[u].insert(g[u].end(), it->second.begin(), it->second.end());
it->second.clear();
}
}
}
for (auto const &w : cycle)
{
for (auto const &[c, e] : edges[w])
if (keys[u].find(c) != keys[u].end())
g[u].insert(g[u].end(), e.begin(), e.end());
else
edges[u][c].insert(edges[u][c].end(), e.begin(), e.end());
}
cycle.clear();
}
else
{
cycle.push_back(u);
in_dfs_path[u] = 0;
return x;
}
}
else
{
is_leaf[u] = 0;
}
}
in_dfs_path[u] = 0;
return UINT32_MAX;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
size_t const n = r.size();
for (size_t i = 0; i < u.size(); ++i)
{
visited[u[i]] = visited[u[i]] || c[i] == r[u[i]];
visited[v[i]] = visited[v[i]] || c[i] == r[v[i]];
}
if (visited.count() < n)
{
vector<int> ans(n);
for (size_t i = 0; i < n; ++i)
ans[i] = !visited[i];
return ans;
}
visited.reset();
for (size_t i = 0; i < n; ++i)
keys[i].insert(r[i]), scc[i].push_back(i);
for (size_t i = 0; i < u.size(); ++i)
{
if (c[i] == r[u[i]])
g[u[i]].push_back(v[i]);
else
edges[u[i]][c[i]].push_back(v[i]);
if (c[i] == r[v[i]])
g[v[i]].push_back(u[i]);
else
edges[v[i]][c[i]].push_back(u[i]);
}
iota(scc_index, scc_index + N, 0);
for (size_t i = 0; i < n; ++i)
is_leaf[i] = 1;
for (size_t i = 0; i < n; ++i)
if (!visited[i])
dfs(i);
size_t smallest = SIZE_MAX;
for (size_t i = 0; i < n; ++i)
if (is_leaf[i] && scc[i].size())
smallest = min(smallest, scc[i].size());
vector<int> ans(n);
for (size_t i = 0; i < n; ++i)
if (is_leaf[i] && scc[i].size() == smallest)
for (auto const &u : scc[i])
ans[u] = 1;
return ans;
}
