#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<bool> vb;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const int MAXN = 300007;
int N, M;
vvi dag;
vi R;
vi P;
vi num, low;
stack<int> st;
vb active;
vector<map<int, vi>> npk; // neighbors per key
vvi nodesInC; // nodes in component
vector<set<int>> keys; // keys per node
vvi todo; // nodes to to from a given node
struct unionfind
{
vi arr;
void init(int _size)
{
arr.resize(_size);
iota(all(arr), 0);
}
int find(int a) { return arr[a] = (arr[a] == a) ? a : find(arr[a]); }
void merge(int a, int b)
{
a = find(a);
b = find(b);
arr[a] = b;
}
};
unionfind uf;
void merge(vi &base, vi &add)
{
if (sz(base) < sz(add))
swap(base, add);
for (int x : add)
base.push_back(x);
add.clear();
}
void merge(set<int> &base, set<int> &add)
{
if (sz(base) < sz(add))
swap(base, add);
for (int x : add)
base.insert(x);
add.clear();
}
void dfs(int v, int &idx)
{
num[v] = low[v] = idx++;
st.push(v);
active[v] = true;
while (!todo[v].empty())
{
while (!todo[v].empty())
{
int u = todo[v].back();
todo[v].pop_back();
if (num[u] == -1)
dfs(u, idx);
if (active[u] && num[u] <= num[v])
low[v] = min(low[v], low[u]);
}
if (low[v] == num[v])
{
// start collecting the component
// poping nodes from the stack
while (st.top() != v)
{
int u = st.top();
st.pop();
// todo
merge(todo[v], todo[u]);
// nodes
merge(nodesInC[v], nodesInC[u]);
// keys
for (int k : keys[u])
if (npk[v].find(k) != npk[v].end())
{
merge(todo[v], npk[v][k]);
npk[v].erase(k);
}
merge(keys[v], keys[u]);
// undone edges
for (auto it : npk[u])
{
if (keys[v].find(it.first) != keys[v].end())
merge(todo[v], it.second);
else
merge(npk[v][it.first], it.second);
}
npk[u].clear();
}
}
}
if (low[v] == num[v])
{
// finish collecting the component
// deactivating all nodes
assert(st.top() == v);
st.pop();
for (int u : nodesInC[v])
active[u] = false;
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
N = sz(r), M = sz(u);
R = r;
keys.resize(N);
for (int i = 0; i < N; ++i)
keys[i].insert(r[i]);
npk.resize(N);
todo.resize(N);
for (int i = 0; i < sz(u); ++i)
{
if (R[u[i]] != c[i])
npk[u[i]][c[i]].push_back(v[i]);
else
todo[u[i]].push_back(v[i]);
if (R[v[i]] != c[i])
npk[v[i]][c[i]].push_back(u[i]);
else
todo[v[i]].push_back(u[i]);
}
// tarjan precomputation
active.assign(N, false);
nodesInC.resize(N);
for (int i = 0; i < N; ++i)
nodesInC[i].push_back(i);
num.assign(N, -1), low.assign(N, -1);
int idx = 0;
for (int i = 0; i < N; ++i)
if (num[i] == -1)
dfs(i, idx);
// gen dag
int comp = 0;
vi belongs(N, -1);
vi size;
vector<set<int>> KC;
for (int i = 0; i < N; ++i)
if (!nodesInC[i].empty())
{
KC.push_back(set<int>());
size.push_back(sz(nodesInC[i]));
for (int x : nodesInC[i])
belongs[x] = comp, KC[comp].insert(R[x]);
++comp;
}
vi out(comp, 0);
for (int i = 0; i < M; ++i)
{
if (belongs[u[i]] == belongs[v[i]])
continue;
int uu = belongs[u[i]];
int vv = belongs[v[i]];
if (KC[uu].find(c[i]) != KC[uu].end())
++out[uu];
if (KC[vv].find(c[i]) != KC[vv].end())
++out[vv];
}
// gen anwer
int mini = N + 1;
for (int i = 0; i < comp; ++i)
if (out[i] == 0)
mini = min(mini, size[i]);
vi ans(N, 0);
for (int i = 0; i < N; ++i)
ans[i] = (out[belongs[i]] == 0 && mini == size[belongs[i]]);
return ans;
}
