//koosaga is god and I'm invincible
//upsolving
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define sz(v) ((int)(v).size())
using namespace std;
const int INF=(int)1e9;
struct dsjs{
vector<int> par;
void init(int n){
par.resize(n);
for (int i=0; i<n; i++)
par[i]=i;
}
int get_par(int v){
if (v==par[v])
return v;
return par[v]=get_par(par[v]);
}
bool my_merge(int a,int b){
a=get_par(a);
b=get_par(b);
if (a==b)
return false;
par[b]=a;
return true;
}
};
vector<stack<int>> psb_edge;
vector<set<pair<int,int>>> impsb_edge;
vector<set<int>> key;
vector<int> nxt;
dsjs idx,graph;
void merge_vertex(int cur,int to){
idx.par[cur]=to;
if (sz(psb_edge[cur])>sz(psb_edge[to]))
swap(psb_edge[cur],psb_edge[to]);
while (!psb_edge[cur].empty()){
psb_edge[to].push(psb_edge[cur].top());
psb_edge[cur].pop();
}
if (sz(impsb_edge[cur])<sz(impsb_edge[to]))
swap(impsb_edge[cur],impsb_edge[to]);
for (auto i=impsb_edge[cur].begin(); i!=impsb_edge[cur].end(); i=impsb_edge[cur].erase(i))
impsb_edge[to].insert(*i);
if (sz(key[cur])>sz(key[to]))
swap(key[cur],key[to]);
for (auto i=key[cur].begin(); i!=key[cur].end(); i=key[cur].erase(i))
key[to].insert(*i);
for (int i:key[to]){
auto it=impsb_edge[to].lower_bound({i,-1});
while (it!=impsb_edge[to].end()&&it->first==i){
psb_edge[to].push(it->second);
it=impsb_edge[to].erase(it);
}
}
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
int n=sz(r);
int m=sz(c);
psb_edge.resize(n*2);
impsb_edge.resize(n*2);
nxt.resize(n*2);
key.resize(n*2);
idx.init(n*2);
graph.init(n*2);
vector<int> ret(n);
for (int i=0; i<m; i++){
if (c[i]==r[u[i]])
psb_edge[u[i]].push(v[i]);
else
impsb_edge[u[i]].insert({c[i],v[i]});
if (c[i]==r[v[i]])
psb_edge[v[i]].push(u[i]);
else
impsb_edge[v[i]].insert({c[i],u[i]});
}
for (int i=0; i<n; i++){
key[i].insert(r[i]);
nxt[i]=i;
if (!psb_edge[i].empty()){
nxt[i]=psb_edge[i].top();
psb_edge[i].pop();
}
}
for (int i=0; i<n; i++){
if (idx.get_par(i)==idx.get_par(nxt[i]))
continue;
if (!graph.my_merge(idx.get_par(i),idx.get_par(nxt[i]))){
for (int j=idx.get_par(i);;){
merge_vertex(j,n);
j=idx.get_par(nxt[j]);
if (j==n)
break;
}
nxt[n]=n;
while (!psb_edge[n].empty()&&idx.get_par(psb_edge[n].top())==n)
psb_edge[n].pop();
if (!psb_edge[n].empty()){
nxt[n]=psb_edge[n].top();
psb_edge[n].pop();
}
n++;
}
}
vector<int> cnt(n);
for (int i=0; i<sz(ret); i++)
cnt[idx.get_par(i)]++;
for (int i=0; i<sz(ret); i++){
ret[i]=INF;
if (idx.get_par(i)==idx.get_par(nxt[i]))
ret[i]=cnt[idx.get_par(i)];
}
int minv=*min_element(all(ret));
for (int i=0; i<sz(ret); i++)
ret[i]=(ret[i]==minv);
return ret;
}
