#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
refs:
https://codeforces.com/blog/entry/92083?#comment-807712
*/
const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
struct DSU {
vector<int> par, rankk, siz;
DSU() {
}
DSU(int n) {
init(n);
}
void init(int n) {
par = vector<int>(n + 1);
rankk = vector<int>(n + 1);
siz = vector<int>(n + 1);
rep(i, n + 1) create(i);
}
void create(int u) {
par[u] = u;
rankk[u] = 0;
siz[u] = 1;
}
int find(int u) {
if (u == par[u]) return u;
else return par[u] = find(par[u]);
}
bool same(int u, int v) {
return find(u) == find(v);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (rankk[u] == rankk[v]) rankk[u]++;
if (rankk[u] < rankk[v]) swap(u, v);
par[v] = u;
siz[u] += siz[v];
}
};
vector<pii> adj[N];
vector<int> node_id(N), up(N);
vector<int> siz(N);
vector<int> nodes[N];
set<int> keys[N];
map<int,vector<int>> mp[N];
vector<int> mp_siz(N);
vector<int> pending[N];
void merge_vectors(vector<int> &v1, vector<int> &v2){
if(sz(v1) < sz(v2)) swap(v1,v2);
trav(x,v2) v1.pb(x);
v2.clear();
}
std::vector<int> find_reachable(std::vector<int> a, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
int n = sz(a), m = sz(U);
rep(i,m){
int u = U[i], v = V[i], w = W[i];
adj[u].pb({v,w}), adj[v].pb({u,w});
}
DSU dsu(n);
set<pii> st;
rep(i,n) st.insert({1,i});
rep(i,n){
node_id[i] = i;
up[i] = i;
siz[i] = 1;
nodes[i].pb(i);
keys[i].insert(a[i]);
for(auto [v,key] : adj[i]){
if(key == a[i]){
pending[i].pb(v);
}
else{
mp[i][key].pb(v);
mp_siz[i]++;
}
}
}
vector<int> ans(n);
int mn_reach = inf1;
while(!st.empty()){
auto [sizu,u] = *st.begin();
if(sizu > mn_reach) break;
st.erase(st.begin());
bool done = false;
while(!pending[u].empty()){
int v = pending[u].back();
pending[u].pop_back();
v = node_id[v];
if(node_id[u] == node_id[v]) conts;
done = true;
if(!dsu.same(u,v)){
// par
up[u] = v;
dsu.merge(u,v);
}
else{
// cyc
vector<int> cyc_nodes;
while(v != u){
cyc_nodes.pb(v);
v = node_id[up[v]];
}
trav(v,cyc_nodes){
node_id[v] = u;
st.erase({siz[v],v});
siz[u] += siz[v];
merge_vectors(pending[u],pending[v]);
merge_vectors(nodes[u],nodes[v]);
if(sz(keys[u])+mp_siz[u] < sz(keys[v])+mp_siz[v]){
swap(keys[u],keys[v]);
swap(mp[u],mp[v]);
swap(mp_siz[u],mp_siz[v]);
}
trav(key,keys[v]){
if(keys[u].count(key)) conts;
keys[u].insert(key);
if(mp[u].count(key)){
auto &curr = mp[u][key];
while(!curr.empty()){
int w = curr.back();
curr.pop_back();
pending[u].pb(w);
mp_siz[u]--;
}
}
}
for(auto [key,adj_nodes] : mp[v]){
auto &curr = mp[u][key];
trav(w,adj_nodes){
curr.pb(w);
mp_siz[u]++;
}
if(keys[u].count(key)){
while(!curr.empty()){
int w = curr.back();
curr.pop_back();
pending[u].pb(w);
mp_siz[u]--;
}
}
}
keys[v].clear();
mp[v].clear();
}
st.insert({siz[u],u});
}
break;
}
if(!done){
if(sizu < mn_reach){
mn_reach = sizu;
}
assert(sizu == mn_reach);
trav(x,nodes[u]){
ans[x] = 1;
}
}
}
return ans;
}
