#include "keys.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
vector<set<pair<int,int>>> adj;
vector<set<int>> C;
vector<vector<int>> adj2;
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
int sz(int x){
return -e[find(x)];
}
bool unite(int a,int b){
//cout<<a<<' '<<b<<'\n';
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
for(auto x:adj[b]){
if(C[a].find(x.f)!=C[a].end()){
adj2[a].push_back(x.s);
}
else{
adj[a].insert(x);
}
}
for(auto x:adj2[b]){
adj2[a].push_back(x);
}
for(auto x:C[b]){
if(C[a].find(x)==C[a].end()){
for(auto it=adj[a].lower_bound({x,0});it!=adj[a].lower_bound({x+1,0});){
it=adj[a].erase(it);
}
}
C[a].insert(x);
}
return true;
}
};
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n=(int)r.size();
int m=(int)u.size();
adj.resize(n);
adj2.resize(n);
C.resize(n);
for(int i=0;i<m;i++){
adj[u[i]].insert({c[i],v[i]});
adj[v[i]].insert({c[i],u[i]});
if(c[i]==r[v[i]]) adj2[v[i]].push_back(u[i]);
if(c[i]==r[u[i]]) adj2[u[i]].push_back(v[i]);
}
for(int i=0;i<n;i++){
C[i].insert(r[i]);
}
DSU dsu(n);
vector<bool> on(n);
vector<bool> vis(n);
vector<bool> qual(n,true);
function<bool(int)> dfs=[&](int v){
vis[v]=true;
on[v]=true;
//cout<<v<<'\n';
while(!adj2[v].empty()){
int u=adj2[v].back();
adj2[v].pop_back();
//cout<<"d "<<v<<' '<<u<<'\n';
u=dsu.find(u);
if(u==v) continue;
if(on[u]){
on[u]=false;
on[v]=false;
return true;
}
if(vis[u]){
qual[v]=false;
continue;
}
if(dfs(u)){
dsu.unite(v,u);
if(on[v]){
on[v]=false;
return true;
}
else{
on[v]=true;
}
}
else{
qual[v]=false;
}
on[v]=false;
v=dsu.find(v);
on[v]=true;
}
on[v]=false;
return false;
};
for(int i=0;i<n;i++){
if(!vis[i]) dfs(i);
//cout<<'\n';
}
int mn=n;
for(int i=0;i<n;i++){
if(qual[dsu.find(i)]) mn=min(mn,dsu.sz(i));
}
vector<int> ans(n);
for(int i=0;i<n;i++){
if(qual[dsu.find(i)] and dsu.sz(i)==mn) ans[i]=1;
}
return ans;
}
