#include <bits/stdc++.h>
using namespace std;
const int nx=3e5+5;
int n, m, dsu[nx], t, vs[nx], have[nx], cnt, p[nx], mn=INT_MAX;
vector<pair<int, int>> d[nx], edg;
vector<int> block[nx], past, past_block, k, res;
queue<int> q;
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
int bfs(int u, int mode)
{
cnt=0;
//for (int i=0; i<n; i++) if (vs[i]||have[i]||!block[i].empty()) cout<<"clear error\n";
vs[u]=1;
past.push_back(u);
q.push(u);
while (!q.empty())
{
auto cu=q.front();
//cout<<"bfs "<<u<<' '<<cu<<'\n';
cnt++;
q.pop();
have[k[cu]]=1;
while (!block[k[cu]].empty())
{
int v=block[k[cu]].back();
block[k[cu]].pop_back();
if (!vs[v])
{
if (find(v)!=find(u)) return v;
vs[v]=1;
past.push_back(v);
q.push(v);
}
}
for (auto [v, w]:d[cu])
{
if (vs[v]) continue;
if (have[w])
{
if (find(v)!=find(u)) return v;
vs[v]=1;
past.push_back(v);
q.push(v);
}
else
{
past_block.push_back(w);
block[w].push_back(v);
}
}
}
if (mode)
{
mn=min(mn, cnt);
for (auto u:past) p[u]=cnt;
}
return -1;
}
void clear()
{
while (!q.empty()) q.pop();
for (auto u:past) vs[u]=0, have[k[u]]=0;
past.clear();
for (auto w:past_block) block[w].clear();
past_block.clear();
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
n=r.size();
m=u.size();
k=r;
for (int i=0; i<n; i++) dsu[i]=i, p[i]=INT_MAX;
for (int i=0; i<m; i++) d[u[i]].push_back({v[i], c[i]}), d[v[i]].push_back({u[i], c[i]});
while (1)
{
edg.clear();
for (int i=0; i<n; i++)
{
if (dsu[i]==i)
{
t=bfs(i, 0);
clear();
if (t!=-1) edg.push_back({i, t});
}
}
if (edg.empty()) break;
for (auto [u, v]:edg) dsu[find(u)]=find(v);
}
//cout<<"debug\n";
for (int i=0; i<n; i++) if (dsu[i]==i) bfs(i, 1), clear();
for (int i=0; i<n; i++) res.push_back(p[i]==mn);
return res;
}
