#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;
template <typename T>
using prq = priority_queue <T>;
template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;
template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }
vec <int> find_reachable(vec <int> r, vec <int> u, vec <int> v, vec <int> c){
int n = sz(r), m = sz(u);
vec <vec <pii>> g(n);
int mx_c = 0;
for (int i = 0; i < m; ++i){
g[u[i]].push_back({v[i], c[i]});
g[v[i]].push_back({u[i], c[i]});
umax(mx_c, c[i]);
}
auto calc = [&](int s){
unordered_map <int, bool> have, us;
unordered_map <int, vec <int>> qu;
vec <int> bfs = {s};
us[s] = 1;
for (int pt = 0; pt < sz(bfs); ++pt){
int u = bfs[pt];
have[r[u]] = 1;
for (auto &v: qu[r[u]]) if (!us[v]){
us[v] = 1;
bfs.push_back(v);
}
qu[r[u]].clear();
for (auto &[v, c]: g[u]) if (!us[v]){
if (have[c]){
us[v] = 1;
bfs.push_back(v);
}
else{
qu[c].push_back(v);
}
}
}
return sz(bfs);
};
if (max(n, m) <= 2000){
int mn = n + 42;
vec <int> f(n);
for (int s = 0; s < n; ++s){
umin(mn, f[s] = calc(s));
}
vec <int> res(n);
for (int i = 0; i < n; ++i){
res[i] = (f[i] == mn);
}
return res;
}
else if (mx_c < 30){
vec <int> msk(n);
for (int i = 0; i < n; ++i){
msk[i] = 1 << r[i];
}
auto sup = [&](int x, int y){
return x == (x | y);
};
vec <tui> bfs;
for (int u = 0; u < n; ++u){
for (auto &[v, c]: g[u]){
if (sup(msk[u], 1 << c)){
bfs.push_back({u, v, c});
}
}
}
for (int pt = 0; pt < sz(bfs); ++pt){
auto [u, v, c] = bfs[pt];
if (sup(msk[u], 1 << c) && !sup(msk[u], msk[v])){
msk[u] |= msk[v];
for (auto &[x, k]: g[u]){
if (sup(msk[u], 1 << k)){
bfs.push_back({u, x, k});
}
}
}
}
vec <vec <int>> gg(n), dd(n);
for (int u = 0; u < n; ++u){
for (auto &[v, c]: g[u]){
if (sup(msk[u], 1 << c)){
gg[u].push_back(v);
dd[v].push_back(u);
}
}
}
vec <bool> us(n);
vec <int> top;
auto dfs = [&](auto &&dfs, int u) -> void{
us[u] = 1;
for (auto &v: gg[u]){
if (!us[v]) dfs(dfs, v);
}
top.push_back(u);
};
for (int i = 0; i < n; ++i){
if (!us[i]) dfs(dfs, i);
}
reverse(all(top));
fill(all(us), 0);
vec <int> cmp(n);
int z = 0;
auto col = [&](auto &&col, int u) -> void{
us[u] = 1;
cmp[u] = z;
for (auto &v: dd[u]){
if (!us[v]) col(col, v);
}
};
for (auto &u: top) if (!us[u]){
col(col, u), ++z;
}
vec <int> deg(z);
for (int u = 0; u < n; ++u){
for (auto &v: gg[u]){
if (cmp[u] != cmp[v]){
++deg[cmp[u]];
}
}
}
vec <int> _f(z, 1e9), f(n, 1e9);
for (int i = 0; i < n; ++i){
if (_f[cmp[i]] == 1e9 && !deg[cmp[i]]){
_f[cmp[i]] = calc(i);
}
}
int mn = 1e9;
for (int i = 0; i < n; ++i){
umin(mn, f[i] = _f[cmp[i]]);
}
vec <int> res(n);
for (int i = 0; i < n; ++i){
res[i] = (f[i] == mn);
}
return res;
}
return {};
}
inline int solve(){
return 0;
}
inline void precalc(){}
