#include <bits/stdc++.h>
//#include "grader.cpp"
#include "keys.h"
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int N = 1e6 + 500;
vector <pair <int, int> > g[N];
set <int> unlocked[N], colors[N];
set <pair <int, int> > locked[N];
int pr[N], prc[N], cnt[N];
int mk[N], to[N];
int n, m, root[N];
bool answer[N];
void get(int c, int u) {
while (1) {
auto it = locked[u].lower_bound(make_pair(c, -1));
if (it == locked[u].end() || it -> F != c) {
break;
}
unlocked[u].insert(it -> S);
locked[u].erase(it);
}
}
int fc(int v) {return (prc[v] == v ? v : prc[v] = fc(prc[v]));}
void link_cyc(int v, int u) {
v = fc(v); u = fc(u);
if (v == u) {
return;
}
if (sz(unlocked[v]) + sz(locked[v]) + sz(colors[v]) > sz(unlocked[u]) + sz(locked[u]) + sz(colors[u])) {
swap(u, v);
}
for (auto &x : unlocked[v]) {
unlocked[u].insert(x);
}
for (auto &x : locked[v]) {
if (colors[u].count(x.F)) {
unlocked[u].insert(x.S);
} else {
locked[u].insert(x);
}
}
for (auto &x : colors[v]) {
if (!colors[u].count(x)) {
colors[u].insert(x);
get(x, u);
}
}
prc[v] = u;
cnt[u] += cnt[v];
}
int f(int v) {return (pr[v] == v ? v : pr[v] = f(pr[v]));}
void link(int v, int u) {
v = f(v); u = f(u);
if (v == u) {
return;
}
pr[v] = u;
}
void go(int c) {
int v = root[c], rt = root[c];
while (!mk[v]) {
mk[v] = 1;
link_cyc(v, to[v]);
v = to[v];
assert(v >= 0);
}
while (sz(unlocked[fc(rt)])) {
int u = fc(*unlocked[fc(rt)].begin());
unlocked[fc(rt)].erase(unlocked[fc(rt)].begin());
if (u == fc(rt)) {
continue;
}
if (f(u) != f(rt)) {
answer[c] = 0;
mk[fc(rt)] = 0;
to[fc(rt)] = u;
link(u, rt);
break;
}
while (!mk[u]) {
mk[u] = 1;
link_cyc(u, rt);
u = to[u];
assert(u >= 0);
}
}
}
vector <int> find_reachable(vector <int> r, vector <int> u, vector <int> v, vector <int> c) {
n = sz(r); m = sz(u);
for (int i = 0; i < m; i++) {
if (u[i] == v[i]) {
continue;
}
g[u[i]].pb({v[i], c[i]});
g[v[i]].pb({u[i], c[i]});
}
vector <int> ans(n, 0);
bool ret = 0;
for (int i = 0; i < n; i++) {
to[i] = -1;
prc[i] = i; cnt[i] = 1;
pr[i] = i;
colors[i].insert(r[i]);
for (auto [u, c] : g[i]) {
if (r[i] == c) {
to[i] = u;
unlocked[i].insert(u);
} else {
locked[i].insert({c, u});
}
}
if (to[i] == -1) {
ans[i] = 1;
ret = 1;
}
}
if (ret) {
return ans;
}
int cmp = 0;
vector <int> nodes;
for (int i = 0; i < n; i++) {
if (mk[i]) {
continue;
}
int v = i;
nodes.clear();
while (!mk[v]) {
mk[v] = 1;
nodes.pb(v);
link(v, to[v]);
v = to[v];
assert(v >= 0);
}
if (mk[v] == 1) {
root[cmp] = v;
cmp++;
}
for (auto v : nodes) {
mk[v] = 2;
}
}
for (int i = 0; i < n; i++) {
mk[i] = 0;
}
for (int i = 0; i < cmp; i++) {
answer[i] = 1;
go(i);
}
int mn = 1e9;
for (int i = 0; i < cmp; i++) {
if (!answer[i]) {
continue;
}
mn = min(mn, cnt[fc(root[i])]);
}
set <int> cmps;
for (int i = 0; i < cmp; i++) {
if (answer[i] && cnt[fc(root[i])] == mn) {
cmps.insert(fc(root[i]));
}
}
for (int i = 0; i < n; i++) {
if (cmps.count(fc(i))) {
ans[i] = 1;
}
}
return ans;
}
