#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=3e5+5;
const int mod=998244353;
const int mxlogN=20;
const int mxK=26;
const int inf=30000;
const int K=600;
struct DSU
{
vector<int> size,p;
int comp;
void build(int n)
{
size=vector<int>(n,1);
p=vector<int>(n);
iota(p.begin(),p.end(),0);
comp=n;
}
int get(int x)
{
if(p[x]^x) p[x]=get(p[x]);
return p[x];
}
bool unite(int a, int b)
{
a=get(a),b=get(b);
if(a==b) return 0;
if(size[a]>size[b]) swap(a,b);
p[a]=b;
size[b]+=size[a];
comp--;
return 1;
}
};
int who[mxN], nex[mxN];
vector<int> conn[mxN];
set<int> keys[mxN];
set<pair<int,int>> doors[mxN];
void add_door(int i, int c, int x)
{
if(keys[i].count(c)) conn[i].push_back(x);
else doors[i].insert({c,x});
}
void add_key(int i, int c)
{
if(!keys[i].count(c))
{
keys[i].insert(c);
auto it=doors[i].upper_bound({c,-1});
while(it!=doors[i].end()&&it->first==c)
{
auto jt=next(it);
conn[i].push_back(it->second);
doors[i].erase(it);
it=jt;
}
}
}
void merge(int u, int v)
{
///prebaci ove u v
///ako ovo neradi probaj sum, pa sve da prebacis
//if(conn[u].size()>conn[v].size()) conn[u].swap(conn[v]);
for(auto x:conn[u]) conn[v].push_back(x);
conn[u].clear();
//if(keys[u].size()>keys[v].size()) keys[u].swap(keys[v]);
for(auto c:keys[u]) add_key(v,c);
keys[u].clear();
//if(doors[u].size()>doors[v].size()) doors[u].swap(doors[v]);
for(auto par:doors[u]) add_door(v,par.first,par.second);
doors[u].clear();
}
int cnt[mxN];
bool can[mxN];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
int n=r.size(),m=u.size();
for(int i=0; i<m; i++)
{
add_door(u[i],c[i],v[i]);
add_door(v[i],c[i],u[i]);
}
for(int i=0; i<n; i++)
{
add_key(i,r[i]);
who[i]=nex[i]=i;
}
DSU dsu; dsu.build(n);
for(int i=0; i<n; i++)
{
while(conn[i].size())
{
int j=who[conn[i].back()];
conn[i].pop_back();
if(dsu.get(i)==dsu.get(j))
{
vector<int> vis;
while(j!=i)
{
int k=who[nex[j]];
who[j]=i;
vis.push_back(j);
j=k;
}
for(int j:vis) merge(j,i);
}
else
{
nex[i]=j;
dsu.unite(i,j);
break;
}
}
}
for(int i=0; i<n; i++) cnt[who[i]]++;
for(int i=0; i<n; i++) can[i]=who[i]==i&&nex[i]==i;
int mn=n+1;
for(int i=0; i<n; i++) if(can[i]) mn=min(mn,cnt[i]);
vector<int> ans(n,0);
for(int i=0; i<n; i++) if(cnt[who[i]]==mn&&can[who[i]]) ans[i]=1;
return ans;
}
/*
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m; cin >> n >> m;
vector<int> r(n),u(m),v(m),c(m);
for(int i=0; i<n; i++) cin >> r[i];
for(int i=0; i<m; i++) cin >> u[i];
for(int i=0; i<m; i++) cin >> v[i];
for(int i=0; i<m; i++) cin >> c[i];
auto ans=find_reachable(r,u,v,c);
for(auto i:ans) cout << i << " ";
cout << "\n";
}
*/
/*
7 10
0 1 1 2 2 1 2
0 0 1 1 2 3 3 4 4 5
1 2 2 3 3 4 5 5 6 6
0 0 1 0 0 1 2 0 2 1
*/
