#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,multiset<int>> v[N];
set<int> s[N];
vector<int> topo,vis(N,0),col(N),par(N),mark(N);
vector<array<int,3>> geri_ekle;
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);
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].insert(u);
int u=dsu.find(a);
if(u!=a){
swap(s[a],s[u]);
swap(v[a],v[u]);
}
}
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);
}
void dfs(int c){
c=dsu.find(c);
if(vis[c]==2) return;
//cout << "vardim: " << c << '\n';
vis[c]=1;
vector<int> go;
vector<array<int,2>> sil;
for(int u:s[c]){
for(int x:v[c][u]){
x=dsu.find(x);
if(vis[x]==2 || x==c) continue;
if(vis[x]==1){
int d=dsu.find(c);
while(dsu.find(d)!=dsu.find(x)){
//cout << "Mergele\n";
//cout << par[d] << ' ' << d << '\n';
dsu.unite(par[d],d);
merge_info(par[d],d);
d=dsu.find(par[d]);
}
}
else{
par[dsu.find(x)]=dsu.find(c);
sil.push_back({u,dsu.find(x)});
geri_ekle.push_back({dsu.find(c),dsu.find(x),u});
go.push_back(dsu.find(x));
}
}
}
for(auto x:sil) v[dsu.find(c)][x[0]].erase(v[dsu.find(c)][x[0]].find(x[1]));
for(int x:go) dfs(dsu.find(x));
vis[dsu.find(c)]=2;
}
void check(int c){
c=dsu.find(c);
if(vis[c]) return;
vis[c]=1;
//cout << "bakcaz: " << c << '\n';
for(int u:s[c]){
for(int x:v[c][u]){
x=dsu.find(x);
//cout << c << " " << x << '\n';
if(x!=c) mark[c]=1;
}
}
}
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].insert(b);
v[b][c].insert(a);
}
for(int i=0;i<n;i++) topo_sort(i);
reverse(all(topo));
vis.assign(N,0);
for(int x:topo) dfs(x);
vis.assign(N,0);
for(auto x:geri_ekle){
int a=x[0],b=x[1],c=x[2];
v[a][c].insert(b);
v[b][c].insert(a);
}
for(int x:topo) check(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].insert(b);
v[b][c].insert(a);
}
for(int i=0;i<n;i++) topo_sort(i);
reverse(all(topo));
vis.assign(N,0);
for(int x:topo) dfs(x);
vis.assign(N,0);
for(auto x:geri_ekle){
int a=x[0],b=x[1],c=x[2];
v[a][c].insert(b);
v[b][c].insert(a);
}
for(int x:topo) check(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;
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;
}*/
