#include "keys.h"
#include <cstdio>
#include <cstring>
#include <vector>
const int N = 300000;
int n, to[N], top[N], go[N], vis[N], size[N];
std::vector<std::pair<int, int> > g[N];
std::vector<int> unlock[N];
bool wascol[N], was[N], need[N];
int find(int v) {
while (top[v] != -1) v = top[v];
return v;
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a != b) top[b] = a;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
n = r.size();
for (int i = 0; i < n; ++i) to[i] = -1;
for (int i = 0; i < (int)u.size(); ++i) {
g[u[i]].push_back(std::make_pair(v[i], c[i]));
g[v[i]].push_back(std::make_pair(u[i], c[i]));
}
std::vector<int> ans(n);
bool any = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (int)g[i].size(); ++j) if (g[i][j].second == r[i]) to[i] = g[i][j].first;
if (to[i] == -1) any = 1;
}
if (any) {
for (int i = 0; i < n; ++i) if (to[i] == -1) ans[i] = 1;
return ans;
}
for (int i = 0; i < n; ++i) {
top[i] = -1;
need[i] = 1;
go[i] = to[i];
}
do {
std::vector<int> ii;
memset(vis, 0, sizeof vis);
int it = 0;
for (int i = 0; i < n; ++i) if (need[i] && !vis[i] && top[i] == -1) {
++it;
int cur = i;
while (!vis[cur]) {
vis[cur] = it;
if (go[cur] == -1) break;
cur = go[cur];
}
if (vis[cur] == it) {
if (go[cur] == -1) ii.push_back(cur);
else {
int start = cur;
do {
merge(cur, go[cur]);
cur = go[cur];
} while (cur != start);
cur = find(cur);
ii.push_back(cur);
}
}
}
memset(need, 0, sizeof need);
for (int i = 0; i < (int)ii.size(); ++i) need[ii[i]] = 1;
any = 0;
for (int i = 0; i < (int)ii.size(); ++i) {
memset(was, 0, sizeof was);
memset(wascol, 0, sizeof wascol);
for (int i = 0; i < n; ++i) unlock[i].clear();
int start = ii[i];
std::vector<int> vec;
vec.push_back(start);
was[start] = 1;
int res = -1;
while (!vec.empty()) {
int v = vec.back();
vec.pop_back();
if (need[find(v)] && find(v) != start) {
res = find(v);
break;
} else if (find(v) != start) top[find(v)] = start;
int c = r[v];
if (!wascol[c]) {
wascol[c] = 1;
for (int i = 0; i < (int)unlock[c].size(); ++i) if (!was[unlock[c][i]]) {
was[unlock[c][i]] = 1;
vec.push_back(unlock[c][i]);
}
}
for (int i = 0; i < (int)g[v].size(); ++i) if (!was[g[v][i].first]) {
if (wascol[g[v][i].second]) {
was[g[v][i].first] = 1;
vec.push_back(g[v][i].first);
} else unlock[g[v][i].second].push_back(g[v][i].first);
}
}
go[start] = res;
if (res != -1) any = 1;
}
} while (any);
for (int i = 0; i < n; ++i) if (need[find(i)]) ++size[find(i)];
int mn = n;
for (int i = 0; i < n; ++i) if (need[i] && top[i] == -1) mn = std::min(mn, size[i]);
for (int i = 0; i < n; ++i) if (need[find(i)] && size[find(i)] == mn) ans[i] = 1;
return ans;
}
