#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 3e5 + 5;
map<int,vector<int>> v[N];
set<int> s[N];
vector<int> topo,vis(N,0),col(N),mark(N,0);
struct DSU{
vector<int> par,siz;
DSU(int n){
par.resize(n);
siz.assign(n,1);
iota(all(par),0);
}
int find(int a){
if(par[a]==a) return a;
return par[a]=find(par[a]);
}
void unite(int a,int b){
a=find(a),b=find(b);
if(a==b) return;
if(siz[a]<siz[b]) swap(a,b);
par[b]=a;
siz[a]+=siz[b];
}
};
DSU dsu(N);
void merge_info(int a,int b){
a=dsu.find(a),b=dsu.find(b);
if(a==b) return;
dsu.unite(a,b);
mark[a]|=mark[b];
if(sz(s[a])<sz(s[b])) swap(s[a],s[b]);
for(int u:s[b]) s[a].insert(u);
int sA=0,sB=0;
for(auto x:v[a]) sA+=sz(x.second);
for(auto x:v[b]) sB+=sz(x.second);
if(sA<sB) swap(v[a],v[b]);
for(auto x:v[b]) for(int u:x.second) v[a][x.first].push_back(u);
if(dsu.find(a)==b){
swap(s[a],s[b]);
swap(mark[a],mark[b]);
swap(v[a],v[b]);
}
}
void topo_sort(int c){
if(vis[c]) return;
vis[c]=1;
for(int x:v[c][col[c]]) topo_sort(x);
topo.push_back(c);
}
vector<int> cur;
void dfs(int c){
c=dsu.find(c);
if(vis[c]==2) return;
//cout << "geldim: " << c << '\n';
cur.push_back(c);
vis[c]=1;
for(int u:s[c]){
while(!v[c][u].empty()){
int x=dsu.find(v[c][u].back());
v[c][u].pop_back();
if(x==c) continue;
if(vis[x]==2 || mark[x]){
mark[c]=1;
return;
}
if(vis[x]==1){
//cout << "Mergele\n";
//cout << c << ' ' << x << '\n';
while(!cur.empty() && dsu.find(cur.back())!=dsu.find(x)){
dsu.unite(cur.back(),x);
merge_info(cur.back(),x);
cur.pop_back();
}
}
else{
dfs(x);
if(dsu.find(c)!=dsu.find(x)) mark[c]=1;
}
}
}
if(!cur.empty() && cur.back()==c) cur.pop_back();
vis[dsu.find(c)]=2;
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){
int n=sz(R),m=sz(U);
for(int i=0;i<n;i++) col[i]=R[i];
for(int i=0;i<n;i++) s[i].insert(col[i]);
for(int i=0;i<m;i++){
int a=U[i],b=V[i],c=C[i];
v[a][c].push_back(b);
v[b][c].push_back(a);
}
for(int i=0;i<n;i++) topo_sort(i);
reverse(all(topo));
vis.assign(N,0);
for(int x:topo) dfs(x);
int mini=100000007;
for(int i=0;i<n;i++){
if(mark[dsu.find(i)]) continue;
mini=min(mini,dsu.siz[dsu.find(i)]);
}
vector<int> ans(n,0);
for(int i=0;i<n;i++) if(!mark[dsu.find(i)] && dsu.siz[dsu.find(i)]==mini) ans[i]=1;
return ans;
}
/*void _(){
int n,m;
cin >> n >> m;
for(int i=0;i<n;i++) cin >> col[i];
for(int i=0;i<n;i++) s[i].insert(col[i]);
for(int i=0;i<m;i++){
int a,b,c;
cin >> a >> b >> c;
v[a][c].push_back(b);
v[b][c].push_back(a);
}
for(int i=0;i<n;i++) topo_sort(i);
reverse(all(topo));
vis.assign(N,0);
for(int x:topo) dfs(x);
int mini=100000007;
//cout << "Basla\n";
for(int i=0;i<n;i++){
//cout << i << ' ' << dsu.find(i) << ' ' << mark[dsu.find(i)] << '\n';
if(mark[dsu.find(i)]) continue;
mini=min(mini,dsu.siz[dsu.find(i)]);
}
vector<int> ans(n,0);
for(int i=0;i<n;i++) if(!mark[dsu.find(i)] && dsu.siz[dsu.find(i)]==mini) ans[i]=1;
for(int i=0;i<n;i++) cout << ans[i] << " \n"[i==n-1];
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
