#include <vector>
#include <bits/stdc++.h>
using namespace std;
class DSU {
private:
vector<int> comp, siz;
public:
DSU(int n) : comp(n), siz(n, 1) {
for (int i = 0; i < n; ++i) comp[i] = i;
}
int getc(int i) {
if (comp[i] != i) comp[i] = getc(comp[i]);
return comp[i];
}
bool join(int a, int b) {
a = getc(a);
b = getc(b);
siz[a] += siz[b];
comp[b] = a;
return true;
}
int compSize(int i) { return siz[getc(i)]; }
};
struct Targets {
set<int> act_outs, keys;
set<pair<int, int>> outs;
};
void merge(int i, int t, DSU& dsu, vector<Targets>& tar) {
i = dsu.getc(i);
t = dsu.getc(t);
assert(i != t);
// Join smaller to larger
int si = tar[i].keys.size() + tar[i].outs.size() + tar[i].act_outs.size();
int st = tar[t].keys.size() + tar[t].outs.size() + tar[t].act_outs.size();
if (si < st) swap(i, t);
dsu.join(i, t);
// Add new keys
for (int key : tar[t].keys) {
auto it = tar[i].outs.lower_bound(make_pair(key, 0));
while(it != tar[i].outs.end() && (*it).first == key) {
tar[i].act_outs.insert((*it).second);
auto tmp = it;
++it;
tar[i].outs.erase(tmp);
}
tar[i].keys.insert(key);
}
// Add new edges
for (int out : tar[t].act_outs) tar[i].act_outs.insert(out);
for (auto pr : tar[t].outs) {
auto it = tar[i].keys.find(pr.first);
if (it != tar[i].keys.end()) tar[i].act_outs.insert(pr.second);
else tar[i].outs.insert(pr);
}
tar[t].act_outs.clear();
tar[t].keys.clear();
tar[t].outs.clear();
}
int dfs(int i, vector<int>& state, DSU& dsu, vector<Targets>& tar) {
state[i] = 1; // Active
while(true) {
i = dsu.getc(i);
/*
cerr << "dfs(" << i << "): ";
for (int t : tar[i].act_outs) cerr << t << ' '; cerr << "/ ";
for (int x : tar[i].keys) cerr << x << ' '; cerr << "/ ";
for (auto pr : tar[i].outs) cerr << pr.first << "," << pr.second << " "; cerr << "\n";
*/
if (tar[i].act_outs.empty()) {
// cerr << "Done, POTENTIAL SMALLEST\n";
state[i] = -1; // Done, potential smallest
return -1;
}
auto it = tar[i].act_outs.begin();
int t = dsu.getc(*it);
tar[i].act_outs.erase(it);
// cerr << "Edge " << i << ' ' << t << ": " << state[t] << endl;
if (t == i) continue;
if (state[t] < 0) {
// cerr << "Done, NOT POTENTIAL SMALLEST\n";
state[i] = -2; // Done, NOT potential smallest
return -1;
} else if (state[t] == 1) {
// cerr << "Found cycle!\n";
return t; // Compress cycle
}
int sub = dfs(t, state, dsu, tar);
if (sub >= 0) {
bool rec = (dsu.getc(sub) != dsu.getc(i));
merge(i, t, dsu, tar);
if (rec) {
// cerr << "Found cycle!\n";
return sub;
}
} else {
// cerr << "Done, NOT POTENTIAL SMALLEST\n";
state[i] = -2; // Done, NOT potential smallest
return -1;
}
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
vector<Targets> tar(n);
for (int i = 0; i < n; ++i) tar[i].keys.insert(r[i]);
for (int j = 0; j < m; ++j) {
if (c[j] == r[u[j]]) tar[u[j]].act_outs.insert(v[j]);
else tar[u[j]].outs.emplace(c[j], v[j]);
if (c[j] == r[v[j]]) tar[v[j]].act_outs.insert(u[j]);
else tar[v[j]].outs.emplace(c[j], u[j]);
}
DSU dsu(n);
vector<int> state(n, 0);
for (int i = 0; i < n; ++i) {
if (state[dsu.getc(i)] == 0) dfs(i, state, dsu, tar);
}
vector<pair<int, int>> ord(n);
for (int i = 0; i < n; ++i) ord[i] = {state[dsu.getc(i)] == -1 ? dsu.compSize(i) : n + 1, i};
sort(ord.begin(), ord.end());
vector<int> res(n, 0);
for (int i = 0; i < n; ++i) res[ord[i].second] |= (ord[i].first == ord[0].first);
return res;
}
