#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 300005;
int n;
vector<pair<int, int> > g[N];
int maxu[N];
bool c[N];
bool cc[N];
vector<int> v[N];
vector<vector<int> > vvv;
int stup(int x, const vector<int>& r)
{
int ans = 0;
queue<int> q;
q.push(x);
queue<int> qq;
vector<int> vv;
int s = x;
while (!q.empty())
{
int x = q.front();
q.pop();
if (c[x])
continue;
++ans;
vv.push_back(x);
qq.push(x);
qq.push(r[x]);
c[x] = true;
cc[r[x]] = true;
maxu[s] = max(maxu[s], maxu[x]);
if (maxu[s] > s)
{
ans = N;
break;
}
while (!v[r[x]].empty())
{
q.push(v[r[x]].back());
v[r[x]].pop_back();
}
for (int i = 0; i < sz(g[x]); ++i)
{
int h = g[x][i].fi;
if (cc[g[x][i].se])
q.push(h);
else
{
qq.push(g[x][i].se);
v[g[x][i].se].push_back(h);
}
}
}
while (!qq.empty())
{
int x = qq.front();
qq.pop();
c[x] = false;
cc[x] = false;
v[x].clear();
}
vvv.push_back(vv);
return ans;
}
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n = sz(R);
int m = sz(U);
std::vector<int> ans(n, 0);
for (int i = 0; i < m; ++i)
{
int x = U[i];
int y = V[i];
if (x == y)
continue;
g[x].push_back(m_p(y, C[i]));
g[y].push_back(m_p(x, C[i]));
}
bool ff = false;
for (int x = 0; x < n; ++x)
{
bool f = false;
for (int i = 0; i < g[x].size(); ++i)
{
if (g[x][i].se == R[x])
{
f = true;
break;
}
}
if (!f)
{
ff = true;
break;
}
}
if (ff)
{
for (int x = 0; x < n; ++x)
{
bool f = false;
for (int i = 0; i < g[x].size(); ++i)
{
if (g[x][i].se == R[x])
{
f = true;
break;
}
}
if (!f)
ans[x] = 1;
}
return ans;
}
for (int x = 0; x < n; ++x)
{
maxu[x] = x;
c[x] = false;
}
vector<int> s;
for (int x = 0; x < n; ++x)
{
s.push_back(stup(x, R));
}
int minu = s[0];
for (int x = 0; x < n; ++x)
minu = min(minu, s[x]);
for (int x = 0; x < n; ++x)
{
if (s[x] == minu)
{
for (int j = 0; j < sz(vvv[x]); ++j)
ans[vvv[x][j]] = 1;
}
}
return ans;
}
