#include "keys.h"
#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
const int N = 300000;
int n, to[N], top[N], go[N], vis[N], size[N], from[N], wascol[N], was[N], leave[N], top1[N];
std::vector<std::pair<int, int> > g[N];
std::vector<int> unlock[N], t[N];
bool need[N];
int find(int v) {
if (top[v] == -1) return v;
return top[v] = find(top[v]);
}
int find1(int v) {
if (top1[v] == -1) return v;
return top1[v] = find1(top1[v]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a != b) top[b] = a;
}
void dfs(int v, int x) {
if (from[v] != -1) return;
from[v] = x;
for (int i = 0; i < (int)t[v].size(); ++i) dfs(t[v][i], x);
}
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;
else t[to[i]].push_back(i);
}
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] = top1[i] = -1;
need[i] = 1;
go[i] = to[i];
}
int it = 0;
do {
++it;
assert(it <= 20);
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;
std::vector<int> vv;
while (!vis[cur]) {
vis[cur] = it;
vv.push_back(cur);
if (go[cur] == -1) break;
cur = go[cur];
if (go[cur] == -1) top1[i] = go[i];
}
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);
}
}
for (int i = 0; i < (int)vv.size(); ++i) if (vv[i] != cur) top1[vv[i]] = cur;
}
memset(need, 0, sizeof need);
for (int i = 0; i < (int)ii.size(); ++i) need[ii[i]] = 1;
for (int i = 0; i < n; ++i) from[i] = find1(i);
any = 0;
int dit = 0;
memset(was, 0, sizeof was);
memset(wascol, 0, sizeof wascol);
std::vector<int> total(n);
for (int i = 0; i < (int)ii.size(); ++i) {
++dit;
int start = ii[i];
std::vector<int> vec;
vec.push_back(start);
was[start] = dit;
int res = -1;
std::vector<int> cc;
while (!vec.empty() && res == -1) {
int v = vec.back();
vec.pop_back();
if (find(v) != start && need[find(v)]) res = find(v);
else if (from[v] != start) res = from[v];
else {
int c = r[v];
if (find(v) != start) top[find(v)] = start;
++total[v];
assert(total[v] < 2);
if (wascol[c] != dit) {
wascol[c] = dit;
for (int i = 0; i < (int)unlock[c].size(); ++i) if (was[unlock[c][i]] != dit) {
int next = unlock[c][i];
was[next] = dit;
vec.push_back(next);
}
}
if (res == -1) for (int i = 0; i < (int)g[v].size(); ++i) if (was[g[v][i].first] != dit) {
if (wascol[g[v][i].second] == dit) {
int next = g[v][i].first;
was[next] = dit;
vec.push_back(next);
} else {
cc.push_back(g[v][i].second);
unlock[g[v][i].second].push_back(g[v][i].first);
}
}
}
}
for (int i = 0; i < (int)cc.size(); ++i) unlock[cc[i]].clear();
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;
}
