#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*3;
const ll MOD = 998244353;
const ll INF = 1e16;
vector<pi> adj[MAXN];
int nx[MAXN], idx[MAXN];
vector<int> pv[MAXN];
vector<int> vtx[MAXN];
set<int> col[MAXN];
vector<int> cnct, pnt;
int root(int x, vector<int>& par) { return par[x]==x?x:par[x]=root(par[x], par); }
void merge(int x, int y, vector<int>& par) {
//x = root(x, par), y = root(y, par);
//if(x^y) par[x]=y;
par[y] = x;
}
void merge_stl(int a, int b) {
merge(a, b, pnt);
for(int x : vtx[b]) {
vtx[a].push_back(x);
} for(int x : col[b]) {
col[a].insert(x);
} vtx[b].clear(); col[b].clear();
}
queue<vector<int> > cycle;
vector<pi> cand;
vector<int> ans;
vector<int> tmp, v;
int vst[MAXN]; // -1: already vst, 0: not vst, 1: current vst
vector<int> track;
void dfs(int here) {
vst[here] = 1;
track.push_back(here);
int there = nx[here];
if(there == -1) return;
if(vst[there] == -1) return;
if(vst[there] == 1) {
tmp.clear();
int i=0; while(track[i]^there) i++;
for(; i<track.size(); i++) tmp.push_back(track[i]);
cycle.push(tmp); return;
} dfs(there);
}
int cnt[MAXN];
int num;
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(), m = u.size(); int 테스트=3; 테스트++;
for(int i=0; i<m; i++) {
adj[u[i]].push_back(pi(v[i], c[i]));
adj[v[i]].push_back(pi(u[i], c[i]));
} for(int i=0; i<n; i++) {
col[i].insert(r[i]);
vtx[i].push_back(i);
}
cnct.resize(n); pnt.resize(n); ans.resize(n);
for(int i=0; i<n; i++) cnct[i] = pnt[i] = i;
// nx init
bool chk = 0;
memset(nx, -1, sizeof nx);
for(int i=0; i<n; i++) {
for(int &j = idx[i]; j<adj[i].size(); j++) {
int x = adj[i][j].ff, w = adj[i][j].ss;
if(w == r[i]) {
nx[i] = x; pv[x].push_back(i);
merge(i, nx[i], cnct); break;
}
} if(nx[i] == -1) {
chk=1; ans[i]=1;
}
} if(chk) return ans;
// find cycle
for(int i=0; i<n; i++) {
if(!vst[i]) {
track.clear();
dfs(i);
for(int x:track) vst[x]=-1;
}
}
while(cycle.size()) {
// union cycle
v = cycle.front(); cycle.pop();
for(int i=1; i<v.size(); i++) {
if(vtx[v[0]].size() < vtx[v[i]].size()) swap(v[0], v[i]);
merge_stl(v[0], v[i]);
}
// update nx and pv
tmp.clear();
for(int a : vtx[v[0]]) {
for(int b : pv[a]) {
if(root(b, pnt) == v[0]) continue;
tmp.push_back(b); nx[b] = v[0];
} pv[a].clear();
} swap(tmp, pv[v[0]]);
// update new nx
bool esc = 0;
tmp.clear();
for(int a : vtx[v[0]]) {
for(int &j = idx[a]; j<adj[a].size(); j++) {
int b = adj[a][j].ff, w = adj[a][j].ss; b = root(b, pnt);
if(b!=v[0] && col[v[0]].find(w)!=col[v[0]].end()) {
int x = root(v[0], cnct), y = root(b, cnct);
if(x == y) {
tmp.push_back(v[0]); num++;
for(int here = b; here != v[0]; here=nx[here]) {
tmp.push_back(here);
assert(cnt[here]!=num); cnt[here]=num;
}
} else {
nx[v[0]] = b; pv[b].push_back(v[0]);
merge(x, y, cnct);
}
esc = 1; break;
}
} if(esc) break;
}
// push new cycle
if(tmp.size() > 1) cycle.push(tmp);
else cand.push_back(pi(vtx[v[0]].size(), v[0]));
}
// return smallest root
sort(all(cand)); int mn = cand[0].ff;
for(auto x:cand) {
if(x.ff==mn) {
for(int y:vtx[x.ss]) ans[y]=1;
}
}
return ans;
}
