#include <bits/stdc++.h>
#define __DEBUG__
#define pb push_back
using namespace std;
constexpr static int SIZE = 300000;
int min_count = SIZE;
vector<array<int, 2>> g[SIZE];
set<array<int, 2>> pending_edges;
bitset<SIZE> searched;
int visited[SIZE];
int keys[SIZE];
int counts[SIZE];
vector<int> r;
int current_node;
int sum = 0;
bool dfs(int node)
{
sum++;
if (counts[node] > min_count || sum > min_count)
{
sum = SIZE + 1;
return false;
}
visited[node] = current_node;
int key = r[node];
if (keys[key] != current_node)
{
keys[key] = current_node;
array<int, 2> sss = {key, 0};
for (auto it = pending_edges.lower_bound(sss); it != pending_edges.end() && (*it)[0] == key; it++)
if (visited[(*it)[1]] != current_node && !dfs((*it)[1]))
return false;
}
for (auto [c, k] : g[node])
{
if (visited[c] == current_node)
continue;
if (keys[k] == current_node)
{
if (!dfs(c))
return false;
}
else
{
pending_edges.insert({k, c});
}
}
return true;
}
void find_count(int node)
{
current_node = node;
sum = 0;
pending_edges.clear();
dfs(node);
counts[node] = sum;
min_count = min(min_count, counts[node]);
}
vector<int> find_reachable(vector<int> rr, vector<int> u, vector<int> v, vector<int> c)
{
r = rr;
int n = r.size(), m = u.size();
for (int i = 0; i < m; i++)
{
g[v[i]].pb({u[i], c[i]});
g[u[i]].pb({v[i], c[i]});
}
int min_count = n;
for (int i = 0; i < n; i++)
{
visited[i] = -1;
keys[i] = -1;
}
for (int i = 0; i < n; i++)
find_count(i);
vector<int> res(n);
for (int i = 0; i < n; i++)
if (counts[i] == min_count)
res[i] = 1;
return res;
}
