#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
struct disjointSet{
int n;
int par[300002];
int sz[300002];
void init(int _n){
n = _n;
for(int i=0; i<=n; i++) par[i] = i, sz[i] = 1;
}
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
sz[x] += sz[y];
par[y] = x;
}
} dsu;
struct Bitset{
unordered_map<int, ll> mp;
Bitset(){}
Bitset(int x){
mp[x>>6] = 1ULL << (x&63);
}
void merge(Bitset &r){
if(mp.size() > r.mp.size()){
for(auto p: r.mp){
mp[p.first] |= p.second;
}
r.mp.clear();
}
else{
for(auto p: mp){
r.mp[p.first] |= p.second;
}
mp.clear();
mp.swap(r.mp);
}
}
bool chk(int x){
return !!(mp[x>>6] & (1ULL << (x&63)));
}
};
int n;
Bitset arr[300002];
vector<pair<int, int> > link[300002];
stack<int> stk;
bool visited[300002];
bool merged[300002];
vector<int> sccVec;
void dfs1(int x){
visited[x] = 1;
for(auto &y: link[x]){
y.first = dsu.find(y.first);
if(visited[y.first] || !arr[x].chk(y.second)) continue;
dfs1(y.first);
}
stk.push(x);
}
void dfs2(int x){
visited[x] = 0;
sccVec.push_back(x);
for(auto &y: link[x]){
y.first = dsu.find(y.first);
if(!visited[y.first] || !arr[y.first].chk(y.second)) continue;
dfs2(y.first);
}
}
void makeSCC(){
for(int i=0; i<n; i++){
if(!visited[i] && !merged[i]) dfs1(i);
}
while(!stk.empty()){
int tmp = stk.top();
stk.pop();
if(!visited[tmp]) continue;
sccVec.clear();
dfs2(tmp);
for(auto x: sccVec){
if(x==tmp) continue;
arr[tmp].merge(arr[x]);
if(link[tmp].size() > link[x].size()){
for(auto p: link[x]) link[tmp].push_back(p);
link[x].clear();
link[x].shrink_to_fit();
}
else{
for(auto p: link[tmp]) link[x].push_back(p);
link[tmp].clear();
link[tmp].shrink_to_fit();
link[x].swap(link[tmp]);
}
dsu.merge(tmp, x);
merged[x] = 1;
}
}
}
bool toOther[300002];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
n = (int)r.size();
for(int i=0; i<n; i++){
arr[i] = Bitset(r[i]);
}
for(int i=0; i<(int)u.size(); i++){
link[u[i]].push_back(make_pair(v[i], c[i]));
link[v[i]].push_back(make_pair(u[i], c[i]));
}
dsu.init(n);
for(int d=0; d<=5; d++){
makeSCC();
}
for(int i=0; i<n; i++){
if(merged[i]) continue;
for(auto y: link[i]){
if(i != dsu.find(y.first) && arr[i].chk(y.second)) toOther[i] = 1;
}
}
int minSize = n+1;
for(int i=0; i<n; i++){
if(!toOther[dsu.find(i)]) minSize = min(minSize, dsu.sz[dsu.find(i)]);
}
vector<int> ans (n);
for(int i=0; i<n; i++){
ans[i] = (!toOther[dsu.find(i)] && dsu.sz[dsu.find(i)] == minSize);
}
return ans;
}
