#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
int n,m;
set<int> vals[300005];
map<int,vector<int>> roads[300005];
vector<int> tovis[300005];
bool vis[300005];
int curr[300005];
// DSU
int root[300005],siz[300005];
int findroot(int x){
if(x!=root[x]){
root[x] = findroot(root[x]);
}
return root[x];
}
void domerge(int a, int b){
a = findroot(a);
b = findroot(b);
if(a==b){
return;
}
if(siz[a]>siz[b]){
swap(a,b);
}
root[a] = b;
siz[b] += siz[a];
for(int i:vals[a]){
vals[b].insert(i);
}
vals[a].clear();
for(int i:tovis[a]){
tovis[b].push_back(i);
}
tovis[a].clear();
for(pair<int,vector<int>> i:roads[a]){
if(vals[b].find(i.first)!=vals[b].end()){
for(int j:i.second){
tovis[b].push_back(j);
}
}
else{
for(int j:i.second){
roads[b][i.first].push_back(j);
}
}
}
roads[a].clear();
curr[b] += curr[a];
}
int toret=-1;
void dfs(int x){
if(curr[x]){
toret = x;
return;
}
vis[x] = true;
curr[x]++;
while(tovis[x].size()>0){
int p = tovis[x].back();
p = findroot(p);
tovis[x].pop_back();
dfs(p);
if(toret!=-1){
domerge(x,p);
x = findroot(x);
p = findroot(p);
toret = findroot(toret);
if(toret==x){
toret = -1;
}
else{
curr[x]--;
return;
}
}
}
curr[x]--;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
n = r.size();
m = u.size();
for(int i=0;i<=n-1;i++){
vals[i].insert(r[i]);
root[i] = i;
siz[i] = 1;
}
for(int i=0;i<=m-1;i++){
roads[u[i]][c[i]].push_back(v[i]);
roads[v[i]][c[i]].push_back(u[i]);
}
bool one=false;
for(int i=0;i<=n-1;i++){
for(int j:roads[i][r[i]]){
tovis[i].push_back(j);
}
roads[i][r[i]].clear();
if(tovis[i].size()==0){
one = true;
}
}
if(one){
vector<int> ret;
for(int i=0;i<=n-1;i++){
if(tovis[i].size()==0){
ret.push_back(1);
}
else{
ret.push_back(0);
}
}
return ret;
}
for(int i=0;i<=n-1;i++){
if(!vis[i] and root[i]==i){
dfs(i);
}
}
vector<int> ret;
int mini=2e9;
for(int i=0;i<=n-1;i++){
if(siz[findroot(i)]==1){
continue;
}
mini = min(mini,siz[findroot(i)]);
}
for(int i=0;i<=n-1;i++){
if(siz[findroot(i)]==mini){
ret.push_back(1);
}
else{
ret.push_back(0);
}
}
return ret;
}
