#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=3e5+10;
const ll mod =998244353 ;
const ll base=3e18;
vector<pll> adj[maxn];
vector<ll> gr[maxn];
ll a[maxn];
ll cntnw=0;
bool dd[maxn];
ll chk[maxn];
bool h[maxn];
// key that we are having
ll par[maxn];
ll ans[maxn];
ll find_par(ll u)
{
if (par[u]<0)
return u;
return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
x=find_par(x);
y=find_par(y);
if (dd[y])
{
dd[x]=1;
return ;
}
assert(x!=y);
par[y]+=par[x];
par[x]=y;
}
bool dosth(ll x)
{
cntnw++;
vector<ll> vt;
vt.pb(x);
chk[x]=cntnw;
h[a[x]]=1;
vector<ll> vtc;
for (int i=0; i<vt.size(); i++)
{
ll u=vt[i];
if (u<base)
{
//if (ult[u]) cout <<"in vt "<<u<<" "<<x<<endl;
for (auto p:adj[u])
{
ll to=p.ff;
ll key=p.ss;
// if (x==270&&u==270&&to==177) cout <<key<<" "<<h[key]<<" "<<a[x]<<endl;
if (chk[to]==cntnw)
continue;
if (h[key])
{
if (find_par(to)!=x)
{
for (auto to:vt)
{
if (to<base)
h[a[to]]=0;
}
for (auto to:vtc)
{
gr[to].clear();
}
dsu(x,find_par(to));
return true;
}
// if (ult[to])cout <<"child of x"<<to<<" "<<u<<" "<<x<<endl;
chk[to]=cntnw;
vt.pb(to);
h[a[to]]=1;
vt.pb(a[to]+base);
}
else
{
vtc.pb(key);
gr[key].pb(to);
}
}
}
else
{
ll keynw=u-base;
for (auto to:gr[keynw])
{
if (chk[to]==cntnw) continue;
if (find_par(to)!=x)
{
for (auto to:vt)
{
if (to<base)
h[a[to]]=0;
}
for (auto to:vtc)
{
gr[to].clear();
}
dsu(x,find_par(to));
return true;
}
// if (ult[to])cout <<"child of x"<<to<<" "<<u<<" "<<x<<endl;
chk[to]=cntnw;
vt.pb(to);
h[a[to]]=1;
vt.pb(a[to]+base);
}
gr[keynw].clear();
}
}
dd[x]=1;
for (auto to:vt)
{
if (to<base)
h[a[to]]=0,ans[to]=vt.size();
}
for (auto to:vtc)
{
gr[to].clear();
}
return false;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
memset(par,-1,sizeof(par));
memset(ans,0x3f,sizeof(ans));
ll n=r.size();
ll m=u.size();
cntnw=0;
vector<int> res;
for (int i=1; i<=m; i++)
{
adj[u[i-1]+1].pb(make_pair(v[i-1]+1,c[i-1]));
adj[v[i-1]+1].pb(make_pair(u[i-1]+1,c[i-1]));
}
for (int i=1; i<=n; i++)
a[i]=r[i-1];
while (1)
{
bool chk=false;
for (int i=1; i<=n; i++)
{
if (!dd[i]&&par[i]<0)
{
chk|=dosth(i);
}
}
if (!chk)
break;
}
ll mn=base;
for (int i=1; i<=n; i++)
mn=min(mn,ans[i]);
for (int i=1; i<=n; i++)
{
adj[i].clear();
dd[i]=0;
chk[i]=0;
if (ans[i]==mn)
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("test.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<<" ";
}*/
/*
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
*/
/*
3
1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1
*/
/*
3
1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1
*/
