#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200000];
bool visited[200000];
int ord[200000], link[200000], h[200000], out[200000];
vector<int> E;
int cnt = 0;
int _find(int x)
{
if(x == link[x]) return x;
return link[x] = _find(link[x]);
}
void _unite(int x, int y)
{
x = _find(x); y = _find(y);
if(x == y) return;
link[x] = y;
h[y] += h[x];
}
int dfs(int x, int c)
{
visited[x] = c;
ord[x] = ++cnt;
int now = cnt;
for(int i : adj[x])
{
if(visited[i] != 0 && visited[i] < c)
{
E.push_back(x);
continue;
}
if(visited[i] == c)
now = min(now, ord[i]);
else
{
int k = dfs(i, c);
if(k > ord[x])
E.push_back(x);
else
{
_unite(x, i);
now = min(now, k);
}
}
}
return now;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
for(int i=0;i<m;i++)
{
if(r[u[i]] == c[i]) adj[u[i]].push_back(v[i]);
if(r[v[i]] == c[i]) adj[v[i]].push_back(u[i]);
}
for(int i=0;i<n;i++)
{
link[i] = i;
h[i] = 1;
}
int color = 0;
for(int i=0;i<n;i++)
{
if(!visited[i]) dfs(i, ++color);
}
for(int i : E)
{
out[_find(i)]++;
}
int S = 500000;
for(int i=0;i<n;i++)
{
int j = _find(i);
if(out[j] == 0) S = min(S, h[j]);
}
vector<int> ans(n);
//for(int i=0;i<n;i++) ans[i] = adj[i].size();
for(int i=0;i<n;i++)
{
int j = _find(i);
if(out[j] == 0 && S == h[j]) ans[i] = 1;
}
return ans;
}
