#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn=4e5+10;
const ll mod =998244353 ;
const ll base=3e18;
set<pll> adj[maxn];
set<ll> key[maxn];
set<ll> adv[maxn];
ll par[maxn];
ll find_par(ll u)
{
if (par[u]==u) return u;
return par[u]=find_par(par[u]);
}
ll dd[maxn];
/*1
1 6
1 4
1 10
2
2 9
3 5
3 7
3 8
2 3
1 1
2 2
3 2
4 1
5 2
6 1
7 2
8 2
9 2
10 1*/
void dsu(ll x,ll y)
{
x=find_par(x);
y=find_par(y);
if (x==y) return ;
// par[x]+=par[y];
par[y]=x;
if (key[y].size()+adj[y].size()+adv[y].size()>key[x].size()+adj[x].size()+adv[x].size())
{
swap(key[x],key[y]);
swap(adj[x],adj[y]);
swap(adv[x],adv[y]);
}
for (auto to:adv[y]) adv[x].insert(to);
for (auto to:key[y])
{
auto it=adj[x].lower_bound(make_pair(to,(ll)0));
while (it!=adj[x].end()&&((*it).ff)==to)
{
adv[x].insert((*it).ss);
it=adj[x].erase(it);
}
key[x].insert(to);
}
for (auto p:adj[y])
{
if (key[x].count(p.ff))
{
adv[x].insert(p.ss);
}
else
{
adj[x].insert(make_pair(p.ff,p.ss));
}
}
key[y].clear();
adj[y].clear();
adv[y].clear();
}
void popfront(ll x)
{
while (!adv[x].empty())
{
auto h=*adv[x].begin();
if (find_par(h)!=x&&find_par(h)!=h)
{
adv[x].insert(find_par(h));
adv[x].erase(h);
}
else if (find_par(h)==x)
{
adv[x].erase(h);
}
else break;
}
}
/*1
6 1 adv of u
1 6 adv of u
4 1 adv of u
1 4 adv of u
10 1 adv of u
1 10 adv of u
2
9 2 adv of u
2 9 adv of u
3 2 adv of u
5 3 adv of u
3 5 adv of u
7 3 adv of u
3 7 adv of u
8 3 adv of u
3 8 adv of u
2 3 adv of u*/
void dosth(ll x)
{
stack<ll> st;
dd[x]=1;
st.push(x);
while (!st.empty())
{
auto u=st.top();
popfront(u);
if (adv[u].empty())
{
dd[u]=2;
st.pop();
continue;
}
ll v=*adv[u].begin();
// cout <<v<<" "<<u<<endl;
adv[u].erase(v);
if (dd[v]==2) continue;
if (dd[v]==1)
{
while(st.top()!=v)
{
dsu(v,st.top());
dd[st.top()]=0;
st.pop();
}
}
else if(dd[v]==0)
{
dd[v]=1;
st.push(v);
}
}
}
ll cnt_all[maxn];
bool chk[maxn];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
// memset(par,-1,sizeof(par));
ll n=r.size();
ll m=u.size();
vector<int> res;
for (int i=1;i<=n;i++)
{
par[i]=i;
dd[i]=0;
key[i].clear();
adv[i].clear();
adj[i].clear();
cnt_all[i]=0;
chk[i]=0;
key[i].insert(r[i-1]);
}
for (int i=1; i<=m; i++)
{
u[i-1]++;
v[i-1]++;
if (key[u[i-1]].count(c[i-1]))
{
adv[u[i-1]].insert(v[i-1]);
}
else
{
adj[u[i-1]].insert(make_pair(c[i-1],v[i-1]));
}
if (key[v[i-1]].count(c[i-1]))
{
adv[v[i-1]].insert(u[i-1]);
}
else
{
adj[v[i-1]].insert(make_pair(c[i-1],u[i-1]));
}
}
for (int i=1;i<=n;i++)
{
if (!dd[i]&&find_par(i)==i)
{
//cout <<i<<endl;
dosth(i);
}
}
/*1 1
2 2
3 2
4 1
5 2
6 1
7 2
8 2
9 2
10 1*/
/*1
0
6 10
2
0
9
3
0
5 7 8 9
4
0
6
5
0
3 9
6
0
1 4 10
7
0
3
8
0
3
9
0
2 3 5
10
0
1 6
*/
for (int i=1;i<=n;i++)
{
cnt_all[find_par(i)]++;
//cout <<i<<" "<<find_par(i)<<endl;
}
for (int i=1;i<=m;i++)
{
ll x=find_par(u[i-1]);
ll y=find_par(v[i-1]);
if (x==y) continue;
if (key[x].count(c[i-1])) chk[x]=1;
if (key[y].count(c[i-1])) chk[y]=1;
}
ll ans=base;
for (int i=1;i<=n;i++)
{
if (i==find_par(i)&&!chk[i])
{
ans=min(ans,cnt_all[i]);
// cout <<"NANI"<<endl;
}
}
for (int i=1;i<=n;i++)
{
if (!chk[find_par(i)]&&cnt_all[find_par(i)]==ans)
{
res.pb(1);
}
else
{
res.pb(0);
}
}
return res;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n, m;
cin>> n>> m;
vector<int> r;
for (int i=1; i<=n; i++)
{
int x;
cin>> x;
r.pb(x);
}
vector<int> u,v,c;
for (int i=1; i<=m; i++)
{
int x, y, w;
cin>> x>> y>> w;
u.pb(x);
v.pb(y);
c.pb(w);
}
vector<int> ans=find_reachable(r,u,v,c);
for (auto to:ans) cout <<to<<" ";
}*/
/*
10 14
0 0 0 0 0 0 0 0 0 0
2 7 0
6 2 0
2 8 0
4 8 0
9 5 0
5 0 0
4 2 0
2 6 0
7 2 0
9 0 0
8 1 0
9 0 0
8 1 0
5 3 0
*/
/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2*/
/*
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
*/
