#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int32_t> rv;rv.resize(arr.size());for (int i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
const int INF = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "keys.h"
vector<int> comp;
vector<int> pp;
int find(int node){
if (comp[node]==node) return node;
return comp[node]=find(comp[node]);
}
int yuk(int node){
if (pp[node]==node) return pp[node];
return pp[node]=yuk(pp[node]);
}
vector<int32_t> find_reachable(vector<int32_t> r, vector<int32_t> u, vector<int32_t> v, vector<int32_t> c) {
int n = r.size();
int m = u.size();
vector<int> par(n);
vector<vector<int>> kard(n);
for (int i = 0; i < n; ++i)
{
kard[i].push_back(i);
}
comp.resize(n);
pp.resize(n);
vector<int> sz(n,1);
iota(par.begin(), par.end(), 0ll);
iota(pp.begin(), pp.end(), 0ll);
iota(comp.begin(), comp.end(), 0ll);
queue<int> op;
vector<set<int>> keys(n);
vector<map<int,vector<int>>> roads(n);
vector<int> ss(n);
vector<vector<int>> ava(n);
for (int i = 0; i < m; i++){
roads[u[i]][c[i]].push_back(v[i]);
roads[v[i]][c[i]].push_back(u[i]);
ss[u[i]]++;
ss[v[i]]++;
}
for (int i = 0; i < n; ++i)
{
op.push(i);
keys[i].insert(r[i]);
for (auto it = roads[i][r[i]].begin(); it != roads[i][r[i]].end(); it++){
ava[i].push_back(*it);
ss[i]--;
}
roads[i].erase(r[i]);
}
vector<int> fin;
int mis = INF;
queue<int> ne;
while (op.size()){
while (op.size()){
int node = op.front();
op.pop();
if (find(node)!=node) continue;
bool bb = true;
while (ava[node].size()){
int nex = ava[node].back();
ava[node].pop_back();
if (find(node)==find(nex)){
nex=yuk(nex);
while (nex!=node){
sz[node]+=sz[nex];
if (kard[node].size()<kard[nex].size()) swap(kard[node],kard[nex]);
for (int j = 0; j < kard[nex].size(); j++){
kard[node].push_back(kard[nex][j]);
}
sz[nex]=0;
kard[nex].clear();
kard[node].push_back(nex);
if (ss[node]<ss[nex]) swap(roads[node],roads[nex]);
for (auto it : roads[nex]){
for (int i = 0; i < it.second.size(); i++){
roads[node][it.first].push_back(it.second[i]);
ss[node]++;
ss[nex]--;
}
}
roads[nex].clear();
//merge roads (done)
//merge keys (done)
if (keys[node].size()<keys[nex].size()) swap(keys[node],keys[nex]);
for (auto it : keys[nex]){
keys[node].insert(it);
}
keys[nex].clear();
//merge ava (done)
for (auto it : keys[node]){
if (!roads[node].count(it)) continue;
for (auto it2 : roads[node][it]){
ava[node].push_back(it2);
ss[node]--;
}
roads[node].erase(it);
}
if (ava[node].size()<ava[nex].size()) swap(ava[node],ava[nex]);
while (ava[nex].size()){
ava[node].push_back(ava[nex].back());
ava[nex].pop_back();
}
//jump parent
pp[nex]=par[nex];
nex=yuk(nex);
}
}
else {
par[node]=nex;
comp[node]=find(nex);
bb=false;
break;
}
}
if (bb){
if (sz[node]==mis){
for (int i = 0; i < kard[node].size(); i++){
fin.push_back(kard[node][i]);
}
}
else if (sz[node]<mis){
mis=sz[node];
fin.clear();
for (int i = 0; i < kard[node].size(); i++){
fin.push_back(kard[node][i]);
}
}
}
}
swap(ne,op);
}
vector<int> ansarr(n,0);
for (int i = 0; i < fin.size(); ++i)
{
ansarr[fin[i]]=1;
}
return ansarr;
}
