#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 500001;
int p[nmax][2];
int sz[nmax][2];
void make_set(int v, int ind){
p[v][ind] = v;
sz[v][ind] = 1;
}
int find_set(int v, int ind){
if(p[v][ind] == v){
return v;
}
return p[v][ind] = find_set(p[v][ind], ind);
}
void union_sets(int a, int b, int ind){
a = find_set(a, ind);
b = find_set(b, ind);
if(a == b)
return;
p[b][ind] = a;
sz[a][ind] += sz[b][ind];
}
vector <pii> empt;
struct node{
map <int,int>mp;
set <int> st;
vector <vector <pii> > edg;
int tot = 0;
int sz;
int p;
node(){
}
node(int x){
sz = 1;
p = x;
tot = 0;
edg.pb(empt);
}
void add_edge(int x, int c){
tot++;
if(!mp[c]){
mp[c] = edg.size();
edg.pb(empt);
}
edg[mp[c]].pb({x, c});
}
void add_color(int x){
st.insert(x);
}
int get_edge(int v){
while(!st.empty()){
int x = *st.begin();
int o = mp[x];
if(!o) {st.erase(st.begin());continue;}
while(!edg[o].empty()){
int u = edg[o].back().f;
edg[o].pop_back();
if(find_set(u, 1) != find_set(v, 1)){
return u;
}
}
st.erase(st.begin());
}
return -1;
}
}vert[nmax];
void merg(int u, int v){
u = find_set(u, 1);
v = find_set(v, 1);
if(vert[v].tot > vert[u].tot){
swap(vert[u].edg, vert[v].edg);
swap(vert[u].tot, vert[v].tot);
swap(vert[u].mp, vert[v].mp);
swap(vert[u].st, vert[v].st);
}
for(auto x : vert[v].edg){
for(auto to : x){
vert[u].add_edge(to.f, to.s);
}
}
for(auto x : vert[v].st){
vert[u].st.insert(x);
}
union_sets(u, v, 1);
}
set <int> roots;
int ans = 1e9;
set <int> good;
bool upd(){
if(roots.empty()){
return false;
}
while(!roots.empty()){
int x = *roots.begin();
int val = vert[x].get_edge(x);
if(val == -1){
if(sz[x][1] < ans){
good.clear();
ans = sz[x][1];
good.insert(x);
}
else if(sz[x][1] == ans){
good.insert(x);
}
roots.erase(roots.begin());
}
else{
if(find_set(x, 0) == find_set(val , 0)){
while(find_set(val, 1) != find_set(x, 1)){
int xx = find_set(val, 1);
merg(x, val);
val = vert[xx].p;
}
}
else{
roots.erase(roots.begin());
vert[x].p = val;
union_sets(val, x, 0);
}
return true;
}
}
return false;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
for(int i = 0; i < n; i++){
vert[i] = {i};
vert[i].add_color(r[i]);
make_set(i, 0);
make_set(i, 1);
}
for(int i = 0; i < u.size(); i++){
vert[u[i]].add_edge(v[i], c[i]);
vert[v[i]].add_edge(u[i], c[i]);
}
for(int i = 0; i < n; ++i)
roots.insert(i);
while(upd()){}
vector <int> ans(n);
for(int i = 0; i < n; ++i){
if(good.find(find_set(i, 1)) != good.end())
ans[i] = 1;
}
return ans;
}
