/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
struct Dsu {
vector<int> s, p;
int sz;
Dsu(int n){
sz = n;
s.resize(n+1, 1);
p.resize(n+1);
for(int i = 0; i <= n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return (p[v] = find(p[v]));
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
s[b] += s[a];
p[a] = b;
sz--;
}
}
};
vector<pii> g[N];
int n, m;
vector<int> find_reachable(vector<int> r, vi u, vi v, vi c){
n = r.size();
m = u.size();
for(int i = 0; i < m; ++i){
g[u[i]].pb({v[i], c[i]});
g[v[i]].pb({u[i], c[i]});
}
mt19937 rng(2134343213);
vector<int> arr(n);
for(int i = 1; i <= n; ++i){
arr[i-1] = i-1;
swap(arr[i-1], arr[uniform_int_distribution<int>(0,i-1)(rng)]);
}
vector<int> vis(n), viss(n), sz(n);
vi op(n);
vector<vector<int>> Q(n);
map<pii, bool> reach;
Dsu d(n);
for(int u: arr){
// cout << u << ' ';
vi used;
vi usedd;
queue<int> q;
q.push(u);
viss[u] = 1;
while(!q.empty()){
int v = q.front();
q.pop();
sz[u]++;
// cout << u << ' ' << v << '\n';
reach[{d.find(u), d.find(v)}] = 1;
while(Q[r[v]].size()){
int x = Q[r[v]].back(); Q[r[v]].pop_back();
if(!viss[x])
q.push(x), viss[x] = 1;
}
used.pb(r[v]);
usedd.pb(v);
op[r[v]] = 1;
bool ok = 1;
for(auto [to, col]: g[v]){
// cout << u << ' ' << v << ' ' << to << ' ' << col << '\n';
if(vis[to] != 0 && op[col]){
ok = 0;
if(vis[to] == 2){
vis[u] = 2;
}
if(vis[to] == 1){
if(reach[{d.find(to), d.find(u)}]){
vis[u] = 1;
d.merge(u, to);
sz[u] = sz[to];
}else{
vis[u] = 2;
}
}
break;
}
used.pb(col);
if(op[col] && !viss[to]){
viss[to] = 1;
q.push(to);
}else if(!viss[to]) Q[col].pb(to);
}
if(!ok) break;
}
if(vis[u] == 0) vis[u] = 1;
// cout << u << ' ';
// cout << sz[u] << ' ' << vis[u] << '\n';
for(int x: used) Q[x].clear(), op[x] = 0;
for(int x: usedd) viss[x] = 0;
used.clear();
usedd.clear();
}
int mn = n;
for(int i = 0; i < n; ++i){
if(vis[i] == 1) mn = min(mn, sz[i]);
}
vector<int> ans(n);
for(int i = 1; i <= n; ++i){
if(vis[i-1]==1 && sz[i-1]==mn) ans[i-1]=1;
}
return ans;
}
