#include <bits/extc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
// #define int long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto __tmp__ = x; cerr << #x << " = " << __tmp__ << endl;}while(0)
// #define endl "\n"
#define unordered_map __gnu_pbds::gp_hash_table
using pii = pair<int, int>;
// const int inf = 1ll << 60;
const int inf = 1 << 30;
const int MOD = 1e9 + 7;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
srand(time(0));
int n = r.size();
int m = u.size();
vector<vector<pii>> adj(n);
for(int i = 0; i < m; i++) {
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
for(auto i : adj) {
random_shuffle(all(i));
}
int best = n;
vector<int> has(n, -1);
vector<vector<int>> todo(n);
vector<int> toclr;
vector<int> vis(n, -1);
vector<bool> done(n);
vector<int> cnt(n, inf);
function<void(int)> trial = [&](int x) {
vector<int> visl;
deque<int> q;
q.push_back(x);
while(q.size()) {
auto cur = q[0]; q.pop_front();
if(vis[cur] == x) continue;
vis[cur] = x;
visl.push_back(cur);
if(visl.size() > best) return;
if(has[r[cur]] != x) {
has[r[cur]] = x;
for(auto i : todo[r[cur]]) {
if(done[i]) return;
q.push_back(i);
}
todo[r[cur]].clear();
}
for(auto e : adj[cur]) {
if(has[e.s] == x) {
if(done[e.f]) return;
q.push_back(e.f);
} else {
if(todo[e.s].empty()) {
toclr.push_back(e.s);
}
todo[e.s].push_back(e.f);
}
}
}
best = visl.size();
for(auto i : visl) {
cnt[i] = min(cnt[i], (int)visl.size());
}
};
vector<int> perm(n);
iota(all(perm), 0);
for(int i = 0; i < m; i++) {
perm.push_back(u[i]);
perm.push_back(v[i]);
}
random_shuffle(all(perm));
for(auto i : perm) {
trial(i);
done[i] = true;
for(auto j : toclr) {
todo[j].clear();
}
toclr.clear();
}
vector<int> ans(n);
for(int i = 0; i < n; i++) {
if(cnt[i] == best) {
ans[i] = 1;
}
}
return ans;
}
// signed main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// for(auto i : find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2})) {
// cout << i << " ";
// }
// cout << endl;
// }
