#include <bits/stdc++.h>
using namespace std;
int a[300003], s[300003];
bool b[300003], B[300003], C[300003];
vector<pair<int, int>> A[300003];
queue<int> p, P, q, Q[300003];
int find(int x){
if(!a[x])return x;
return a[x] = find(a[x]);
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int N = r.size();
int M = c.size();
for(int i = 0; i < M; i++){
A[u[i]+1].push_back(make_pair(v[i]+1, c[i]));
A[v[i]+1].push_back(make_pair(u[i]+1, c[i]));
}
int T = 20;
while(T--){
for(int t = 1; t <= N; t++){
if(a[t] || C[t])continue;
q.push(t);
while(!q.empty()){
int h = q.front();
q.pop();
if(find(h) != t){
a[t] = h;
C[find(t)] = true;
while(!q.empty())q.pop();
break;
}
B[h] = true;
P.push(h);
if(!b[r[h-1]]){
while(!Q[r[h-1]].empty()){
q.push(Q[r[h-1]].front());
Q[r[-1]].pop();
}
b[r[h-1]] = true;
p.push(r[h-1]);
}
for(int i = 0; i < A[h].size(); i++){
if(B[A[h][i].first])continue;
p.push(A[h][i].second);
if(b[A[h][i].second])q.push(A[h][i].first);
else Q[A[h][i].second].push(A[h][i].first);
}
}
while(!p.empty()){
int h = p.front();
p.pop();
b[h] = false;
while(!Q[h].empty())Q[h].pop();
}
while(!P.empty()){
int h = P.front();
P.pop();
B[h] = false;
}
}
for(int i = 1; i <= N; i++)C[i] = false;
//for(int i = 1; i <= N; i++)cout << a[i] << " ";cout << "\n";
}
for(int t = 1; t <= N; t++){
if(a[t])continue;
q.push(t);
while(!q.empty()){
int h = q.front();
q.pop();
B[h] = true;
s[t]++;
P.push(h);
if(!b[r[h-1]]){
while(!Q[r[h-1]].empty()){
q.push(Q[r[h-1]].front());
Q[r[-1]].pop();
}
b[r[h-1]] = true;
p.push(r[h-1]);
}
for(int i = 0; i < A[h].size(); i++){
if(B[A[h][i].first])continue;
p.push(A[h][i].second);
if(b[A[h][i].second])q.push(A[h][i].first);
else Q[A[h][i].second].push(A[h][i].first);
}
}
while(!p.empty()){
int h = p.front();
p.pop();
b[h] = false;
while(!Q[h].empty())Q[h].pop();
}
while(!P.empty()){
int h = P.front();
P.pop();
B[h] = false;
s[h] = s[t];
}
}
int z = N;
for(int i = 1; i <= N; i++)if(s[i])z=min(z, s[i]);
vector<int> S;
for(int i = 1; i <= N; i++)S.push_back(s[i]==z?1:0);
return S;
}
