#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int M = 300'010;
vector<int> rep(M,1), sajz(M,1);
vector<int> key(M);
vector<vector<pair<int, int>>> g(M);
vector<vector<int>> edges(M);
int best = 0;
int Find(int v) {
return rep[v]==v?v:rep[v]=Find(rep[v]);
}
int Union(int a, int b) {
if(Find(a)!=a) return 0;
rep[a] = Find(b);
return 1;
}
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> C) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for(int i=0; i<M; ++i) rep[i] =i;
int n = R.size();
int m = u.size();
for(int i=0; i<n; ++i) {
key[i] = R[i];
}
for(int i=0; i<m; ++i) {
int a = u[i]; int b = v[i]; int c = C[i];
g[a].push_back({b,c});
g[b].push_back({a,c});
}
vector<int> roots;
for(int i=0; i<n; ++i) roots.push_back(i);
bool flaga = 1;
while(flaga) {
flaga = 0;
vector<pair<int, int>> lista;
vector<int> vis(M);
for(auto r : roots) {
map<int, vector<int>> blocked;
queue<int> Q; Q.push(r);
set<int> keys;
while(Q.size()) {
int v = Q.front(); Q.pop();
vis[v] = 1;
while(blocked[key[v]].size()) {
int u = blocked[key[v]].back();
blocked[key[v]].pop_back();
if(Find(u)!=r) lista.push_back({r,Find(u)});
else if(!vis[u]) { vis[u] =1; Q.push(u);}
}
keys.insert(key[v]);
for(auto[u, c] : g[v]) {
if(keys.find(c)==keys.end()) blocked[c].push_back(u);
else {
if(Find(u)!=r) lista.push_back({r,Find(u)});
else if(!vis[u]) { vis[u] = 1; Q.push(u);}
}
}
}
}
vector<int> used(n);
for(auto[a,b] : lista) {
if(Union(a,b)) { flaga = 1; used[a] = used[b] = 1; }
}
vector<int> nr;
for(auto i : roots) if(i==Find(i) && used[i]) nr.push_back(i);
swap(roots, nr);
}
vector<int> nr;
for(int i=0; i<n; ++i) if(i==Find(i)) nr.push_back(i);
swap(roots, nr);
// for(int i=0; i<n; ++i) cout << Find(i) << " "; cout << "\n";
vector<int> vis(M);
vector<int> ans(n);
vector<int> ile(M, M+1);
int best = M;
for(auto r : roots) {
map<int, vector<int>> blocked;
queue<int> Q; Q.push(r);
set<int> keys;
int cnt = 0;
vector<int> seen;
while(Q.size()) {
int v = Q.front(); Q.pop();
vis[v] = 1; cnt++;
seen.push_back(v);
while(blocked[key[v]].size()) {
int u = blocked[key[v]].back();
blocked[key[v]].pop_back();
if(!vis[u]) { vis[u] = 1; Q.push(u);}
}
keys.insert(key[v]);
for(auto[u, c] : g[v]) {
if(keys.find(c)==keys.end()) blocked[c].push_back(u);
else {
if(!vis[u]) { vis[u] =1; Q.push(u);}
}
}
}
for(auto x : seen) {
ile[x] = cnt;
}
best = min(best, cnt);
}
for(int i=0; i<n; ++i) if(ile[i]==best) ans[i] = 1;
return ans;
}
