#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
int p[300300], p2[300300], sz[300300], nxt[300300];
vector<int> nq[300300];
set<int> k[300300];
set<pair<int, int>> s[300300];
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
int find2(int x) {
return x == p2[x] ? x : p2[x] = find2(p2[x]);
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return false;
// TODO : small to large optimization
if(k[x].size() + s[x].size() < k[y].size() + s[y].size()) swap(x, y);
p[y] = x, sz[x] += sz[y];
for(const auto &kv : k[y]) {
if(k[x].insert(kv).second) {
auto it = s[x].lower_bound({kv, 0});
while(it != s[x].end() && it->first == kv) {
nq[x].push_back(it->second), it = s[x].erase(it);
}
}
}
for(const auto &[col, to] : s[y]) {
if(k[x].count(col)) {
nq[x].push_back(to);
} else {
s[x].insert({col, to});
}
}
if(nq[x].size() > nq[y].size()) swap(nq[x], nq[y]);
for(const auto &nqv : nq[y]) nq[x].push_back(nqv);
return true;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size(), m = v.size();
for(int i=0;i<m;i++) {
s[u[i]].insert({c[i], v[i]});
s[v[i]].insert({c[i], u[i]});
}
queue<int> q;
for(int i=0;i<n;i++) {
q.push(i), p[i] = i, p2[i] = i, sz[i] = 1, nxt[i] = -1;
k[i].insert(r[i]);
auto it = s[i].lower_bound({r[i], 0});
while(it != s[i].end() && it->first == r[i]) {
nq[i].push_back(it->second), it = s[i].erase(it);
}
}
while(!q.empty()) {
int u = find(q.front()); q.pop();
if(nxt[u] != -1) continue;
while(!nq[u].empty()) {
int x = find(nq[u].back()); nq[u].pop_back();
if(u == x) continue;
if(find2(x) == u) {
for(int i=x;i!=u;i=nxt[i]) merge(u, i);
u = find(u), nxt[u] = -1, p2[u] = u;
q.push(u);
} else {
nxt[u] = p2[u] = x;
}
break;
}
}
int mn = 1e9;
for(int i=0;i<n;i++) if(nxt[find(i)] == -1) mn = min(mn, sz[p[i]]);
vector<int> ans(n, 0);
for(int i=0;i<n;i++) if(nxt[p[i]] == -1 && sz[p[i]] == mn) ans[i] = 1;
return ans;
}
