#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
vvpi cant_visit;
class UF {
public:
int n;
int ncomps;
vi par;
vi csize;
vi root;
UF(int a_n): n(a_n), ncomps(a_n), par(a_n, 0), csize(a_n, 1), root(a_n, 0) {
for(int i = 0; i < n; i++) root[i] = par[i] = i;
}
int find(int i) {
return (i == par[i] ? i : par[i] = find(par[i]));
}
int find_root(int i) {
return root[find(i)];
}
int conn(int i, int j) {
return find(i) == find(j);
}
// By convention, set j as the root
void unify(int i, int j) {
int pari = find(i), parj = find(j);
if(pari == parj) return;
root[j] = root[parj];
root[i] = root[pari] = root[parj];// = root[parj];
if(csize[pari] < csize[parj]) {
par[pari] = parj;
csize[parj] += csize[pari];
} else {
par[parj] = pari;
csize[pari] += csize[parj];
}
ncomps--;
}
};
pi bfs_terminate_early(int n, int m, int s, const vi& r, const vvpi& adj, UF& uf) {
set<int> found_k;
set<int> to_delete;
vb vis(n, false);
queue<pi> q;
q.push({s, r[s]});
while(!q.empty()) {
auto [i, cr] = q.front();
q.pop();
if(vis[i]) continue;
vis[i] = true;
if(uf.find_root(i) != s) {
for(int k : to_delete) {
cant_visit[k].clear();
}
return {s, uf.find_root(i)};
}
if(found_k.count(r[i]) == 0) {
while(cant_visit[r[i]].size() > 0) {
q.push(cant_visit[r[i]].back());
cant_visit[r[i]].pop_back();
}
found_k.insert(r[i]);
to_delete.erase(r[i]);
}
for(auto [j, c] : adj[i]) {
if(vis[j]) continue;
if(found_k.count(c) > 0) q.push({j, c});
else {
cant_visit[c].pb({j, c});
to_delete.insert(c);
}
}
}
for(int k : to_delete) {
cant_visit[k].clear();
}
return {-1, -1};
}
int bfs(int n, int m, int s, const vi& r, const vvpi& adj, vb& vis, vi& ans) {
int num = 0;
set<int> found_k;
set<int> to_delete;
queue<pi> q;
q.push({s, r[s]});
stack<int> to_mark;
while(!q.empty()) {
auto [i, cr] = q.front();
q.pop();
if(vis[i]) continue;
vis[i] = true;
to_mark.push(i);
num++;
if(found_k.count(r[i]) == 0) {
while(cant_visit[r[i]].size() > 0) {
q.push(cant_visit[r[i]].back());
cant_visit[r[i]].pop_back();
}
found_k.insert(r[i]);
to_delete.erase(r[i]);
}
for(auto [j, c] : adj[i]) {
// cout << i << " " << j << " " << c << " " << s << "\n";
if(vis[j]) continue;
if(found_k.count(c) > 0) q.push({j, c});
else {
cant_visit[c].pb({j, c});
to_delete.insert(c);
}
}
}
for(int k : to_delete) {
cant_visit[k].clear();
}
while(!to_mark.empty()) {
ans[to_mark.top()] = num;
to_mark.pop();
}
return num;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = r.size(), m = u.size();
vi ans(n, INF(int));
vvpi adj;
for(int i = 0; i < n; i++) {
vpi adjr;
adj.pb(adjr);
}
for(int i = 0; i < n; i++) {
vpi cant_visitr;
cant_visit.pb(cant_visitr);
}
for(int i = 0; i < m; i++) {
adj[u[i]].pb({v[i], c[i]});
adj[v[i]].pb({u[i], c[i]});
}
UF uf(n);
// vb vis(n, false);
for(int rep = 0; rep < 20; rep++) {
vpi to_adjoin;
// Do the BFS chuchu here
for(int s = 0; s < n; s++) {
if(uf.find_root(s) == s) {
// vis[s] = true;
auto [x, y] = bfs_terminate_early(n, m, s, r, adj, uf);
if(x != -1) {
to_adjoin.pb({x, y});
}
}
}
// Unify components
for(auto [x, root] : to_adjoin) {
uf.unify(x, root);
}
}
// for(int i = 0; i < n; i++) {
// cout << uf.find_root(i) << " ";
// }
// cout << "\n";
vb vis_bfs(n, false);
for(int s = 0; s < n; s++) {
if(!vis_bfs[s] && uf.find_root(s) == s) {
bfs(n, m, s, r, adj, vis_bfs, ans);
}
}
int mn = INF(int);
for(int i = 0; i < n; i++) {
mn = min(mn, ans[i]);
}
for(int i = 0; i < n; i++) {
ans[i] = (ans[i] == mn ? 1 : 0);
}
return ans;
}
