#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=300007;
int rep[N];
int Find(int v)
{
if(rep[v]==v) return v;
return rep[v]=Find(rep[v]);
}
void Union(int u,int v)
{
u=Find(u),v=Find(v);
rep[u]=v;
}
set<int>keys[N];
vector<int>E[N];
set<pair<int,int>>edges[N];
int r[N];
vector<int>X[N];
vector<pair<int,int>>ans;
deque<int>Q;
void Merge(int u,int v)
{
if(sz(X[u])>sz(X[v])) swap(u,v);
for(auto x:E[u]) E[v].pb(x);
for(auto x:keys[u])
{
keys[v].insert(x);
while(true)
{
pair<int,int>p=*edges[v].lower_bound({x,0});
if(p.st!=x) break;
edges[v].erase(p);
E[v].pb(p.nd);
}
}
for(auto [c,x]:edges[u])
{
if(keys[v].count(c)) E[v].pb(x);
else edges[v].insert({c,x});
}
for(auto x:X[u])
{
X[v].pb(x);
r[x]=v;
}
while(sz(E[v])>0)
{
if(r[E[v].back()]==v) E[v].pop_back();
else break;
}
if(sz(E[v])>0)
{
if(Find(v)==Find(r[E[v].back()])) Q.pb(v);
else Union(v,r[E[v].back()]);
}
else
{
for(auto x:X[v]) ans.pb({sz(X[v]),x});
}
}
vector<int>find_reachable(vector<int>K,vector<int>U,vector<int>V,vector<int>C)
{
int n=sz(K),m=sz(U);
for(int i=0;i<n;i++)
{
rep[i]=i;
X[i].pb(i);
r[i]=i;
keys[i].insert(K[i]);
edges[i].insert({inf,0});
}
for(int i=0;i<m;i++)
{
if(keys[U[i]].count(C[i])) E[U[i]].pb(V[i]);
else edges[U[i]].insert({C[i],V[i]});
if(keys[V[i]].count(C[i])) E[V[i]].pb(U[i]);
else edges[V[i]].insert({C[i],U[i]});
}
for(int i=0;i<n;i++)
{
if(sz(E[i])==0) ans.pb({1,i});
else
{
if(Find(i)==Find(E[i].back())) Q.pb(i);
else Union(i,E[i].back());
}
}
while(sz(Q)>0)
{
int v=Q[0];
Q.pop_front();
int x=v;
vector<int>C;
while(true)
{
C.pb(x);
x=r[E[r[x]].back()];
if(x==v) break;
}
for(int i=1;i<sz(C);i++) Merge(r[C[i]],r[C[i-1]]);
}
sort(all(ans));
vector<int>res(n,0);
for(auto [k,i]:ans) if(k==ans[0].st) res[i]=1;
return res;
}
/*
int main()
{
int n,m;
cin>>n>>m;
vector<int>K(n);
for(int i=0;i<n;i++) cin>>K[i];
vector<int>U(m),V(m),C(m);
for(int i=0;i<m;i++) cin>>U[i]>>V[i]>>C[i];
vector<int>X=find_reachable(K,U,V,C);
for(auto x:X) cout<<x<<" ";
cout<<endl;
return 0;
}
*/
