#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
struct DSU{
int par[N], setsize[N];
void reset(int n){
for(int i = 0; i < n; i++) par[i] = i, setsize[i] = 1;
}
int setfind(int a){
if(a == par[a]) return a;
else return par[a] = setfind(par[a]);
}
void setunion(int a, int b){
a = setfind(a), b = setfind(b);
if(a != b){
if(setsize[b] > setsize[a]) swap(a, b);
par[b] = par[a];
setsize[a] += setsize[b];
}
}
};
DSU dsu;
struct Edge{
int b, key;
};
vector<Edge> graph[N];
set<int> samekey[N], curnodes;
vector<int> curedges[N], nodestocheck, seenkeys;
bool keyflag[N];
void setkey(int key){
if(keyflag[key] == false){
keyflag[key] = true;
for(auto v : curedges[key]) nodestocheck.push_back(v);
curedges[key].clear();
}
}
vector<int> find_reachable(vector<int> inp_r, vector<int> inp_u, vector<int> inp_v, vector<int> inp_c){
int n = inp_r.size(), m = inp_u.size();
vector<int> ans(n, 0);
dsu.reset(n);
for(int i = 0; i < m; i++){
graph[inp_u[i]].push_back({inp_v[i], inp_c[i]});
if(inp_c[i] == inp_r[inp_u[i]]) samekey[inp_u[i]].insert(inp_v[i]);
graph[inp_v[i]].push_back({inp_u[i], inp_c[i]});
if(inp_c[i] == inp_r[inp_v[i]]) samekey[inp_v[i]].insert(inp_u[i]);
}
for(int v = 0; v < n; v++){
if(dsu.setsize[dsu.setfind(v)] != -1){
bool isbad = false;
curnodes.insert(v);
for(auto e : graph[v]){
curedges[e.key].push_back(e.b);
seenkeys.push_back(e.key);
}
setkey(inp_r[v]);
while(!nodestocheck.empty()){
int u = nodestocheck.back();
nodestocheck.pop_back();
if(dsu.setfind(v) == dsu.setfind(u)) continue;
if(dsu.setsize[dsu.setfind(u)] == -1){
isbad = true;
goto skip;
}
bool flag = false;
if(curnodes.size() <= samekey[u].size()){
for(auto w : curnodes){
if(samekey[u].find(w) != samekey[u].end()){
flag = true;
break;
}
}
}
else{
for(auto w : samekey[u]){
if(curnodes.find(w) != curnodes.end()){
flag = true;
break;
}
}
}
if(flag){
curnodes.insert(u);
dsu.setunion(v, u);
for(auto e : graph[u]){
if(keyflag[e.key]) nodestocheck.push_back(e.b);
else curedges[e.key].push_back(e.b);
seenkeys.push_back(e.key);
}
setkey(inp_r[u]);
}
else{
isbad = true;
goto skip;
}
}
skip:
if(isbad) dsu.setsize[dsu.setfind(v)] = -1;
for(auto key : seenkeys){
curedges[key].clear();
keyflag[key] = false;
}
curnodes.clear(), nodestocheck.clear(), seenkeys.clear();
}
}
int mn = n + 1;
for(int v = 0; v < n; v++){
if(dsu.setsize[dsu.setfind(v)] != -1){
mn = min(mn, dsu.setsize[dsu.setfind(v)]);
}
}
for(int v = 0; v < n; v++){
if(dsu.setsize[dsu.setfind(v)] == mn){
ans[v] = 1;
}
}
return ans;
}
