/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
struct Dsu {
vector<int> s, p;
int sz;
Dsu(int n){
sz = n;
s.resize(n+1, 1);
p.resize(n+1);
for(int i = 0; i <= n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return (p[v] = find(p[v]));
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
s[b] += s[a];
p[a] = b;
sz--;
}
}
};
vector<pii> g[N];
int n, m;
vector<int> BLOCK[N], is_key(N), vis(N);
int search(int root, vector<int> &is_root, int finish, vi &r){
vi used_key, used_vis, used_block;
queue<int> q;
q.push(root);
vis[root] = 1;
used_vis.pb(root);
int sz = 0;
while(q.size()){
int v = q.front(); q.pop();
if(is_key[r[v]] == 0) used_key.pb(r[v]);
is_key[r[v]] = 1;
if(finish == 2) is_root[v] = 1;
++sz;
while(BLOCK[r[v]].size()){
int u = BLOCK[r[v]].back(); BLOCK[r[v]].pop_back();
if(vis[u] == false){
vis[u] = true;
used_vis.pb(u);
q.push(u);
}
}
for(auto [u, col]: g[v]){
if(!vis[u]){
if(is_key[col]){
vis[u] = 1;
used_vis.pb(u);
q.push(u);
if(finish && is_root[u]){
for(int x: used_block) BLOCK[x].clear();
for(int x: used_key) is_key[x] = 0;
for(int x: used_vis) vis[x] = 0;
return u;
}
}else{
BLOCK[col].pb(u);
used_block.pb(col);
}
}
}
}
for(int x: used_block) BLOCK[x].clear();
for(int x: used_key) is_key[x] = 0;
for(int x: used_vis) vis[x] = 0;
if(finish == 0) return sz;
return -1;
}
vector<int> find_reachable(vector<int> r, vi u, vi v, vi c){
n = r.size();
m = u.size();
for(int i = 0; i < m; ++i){
g[u[i]].pb({v[i], c[i]});
g[v[i]].pb({u[i], c[i]});
}
Dsu d(n);
vector<int> is_root(n, 1);
bool OK = true;
while(OK){
OK = false;
vector<pii> P;
for(int i = 0; i < n; ++i){
if(is_root[i]){
auto p = search(i, is_root, 1, r);
if(p != -1) P.pb({i, p});
}
}
for(auto [u, v]: P){
if(d.find(u) != d.find(v)){
d.merge(u, v);
is_root[u] = false;
OK = true;
}
}
}
int sz = n;
vector<int> good(n), ans(n);
for(int i = 0; i < n; ++i){
if(is_root[i]){
sz = min(sz, search(i, is_root, 0, r));
good[d.find(i)] = 1;
}
}
for(int i = 0; i < n; ++i){
if(is_root[i]){
if(search(i, is_root, 0, r) == sz){
search(i, ans, 2, r);
}
}
}
return ans;
}
