#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<long double>
using namespace std;
const int mxn=3e5+5;
vector<pii>g[mxn];
vector<int>rr;
int pr[mxn]{0},n,m,tt[mxn]{0};
bool use[mxn]{0},vis[mxn]{0};
vector<int>usek,usen,useb;
vector<int>key[mxn];
vector<pii>uni;
queue<int>q;
int rs=1e9;
int get(int r){
return pr[r]==r?r:pr[r]=get(pr[r]);
}
void bfs(int st){
q.push(st);
bool ed=0;
while(!q.empty()){
auto u=q.front();q.pop();
if(vis[u])continue;
if(!use[rr[u]]){
use[rr[u]]=1,usek.pb(rr[u]);
while(!key[rr[u]].empty()){
if(!vis[key[rr[u]].back()])q.push(key[rr[u]].back());
key[rr[u]].pop_back();
}
}
if(get(u)!=get(st))uni.pb({st,u}),ed=1;
vis[u]=1;usen.pb(u);
if(ed)break;
for(auto [v,c]:g[u]){
if(vis[v])continue;
else if(!use[c])key[c].pb(v),useb.pb(c);
else q.push(v);
}
}while(!q.empty())q.pop();
for(auto it : useb)key[it].clear();
for(auto it : usek)use[it]=0;
for(auto it : usen)vis[it]=0;
useb.clear();usek.clear();usen.clear();
}
void bfs2(int st){
q.push(st);
while(!q.empty()){
auto u=q.front();q.pop();
if(vis[u])continue;
if(!use[rr[u]]){
use[rr[u]]=1,usek.pb(rr[u]);
while(!key[rr[u]].empty()){
if(!vis[key[rr[u]].back()])q.push(key[rr[u]].back());
key[rr[u]].pop_back();
}
}vis[u]=1;tt[st]++;
for(auto [v,c]:g[u]){
if(vis[v])continue;
else if(!use[c])key[c].pb(v),useb.pb(c);
else q.push(v);
}
}while(!q.empty())q.pop();
for(auto it : useb)key[it].clear();
for(auto it : usek)use[it]=0;
useb.clear();usek.clear();usen.clear();
rs=min(rs,tt[st]);
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c){
n=r.size(),m=u.size();iota(pr,pr+n,0);rr=r;vector<int>ans;ans.resize(n,0);
for(int i=0;i<m;i++){
g[u[i]].pb({v[i],c[i]});
g[v[i]].pb({u[i],c[i]});
}bool dn=0;
while(!dn){
for(int i=0;i<n;i++){
if(get(i)==i)bfs(i);
}
if(uni.empty())dn=1;
if(dn)break;
for(auto [a,b] : uni){
pr[get(a)]=get(b);
}uni.clear();
}
for(int i=0;i<n;i++){
if(get(i)==i)bfs2(i);
}
for(int i=0;i<n;i++)if(vis[i]&&tt[get(i)]==rs)ans[i]=1;
return ans;
}
/*int main(){
vector<int>x=find_reachable({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});
for(auto it : x)cout<<it<<' ';
}*/
