#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
//#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define st first
#define nd second
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define N 300005
#define M 30
const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;
int par[N], sz[N], vis[N], vis2[N];
int keys[N][M];
set<pii> edges[N];
set<int> adj[N], rev_adj[N]; //->{key, node}
vector<int> tomerge[N];
int SIZE;
int find(int node){
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void uni(int a, int b){
a = find(a), b = find(b);
if (a == b) return;
SIZE--;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
for (int i = 0; i < M; i++) keys[a][i] |= keys[b][i];
if (edges[b].size() > edges[a].size()) edges[a].swap(edges[b]);
for (auto i : edges[b]) edges[a].insert({i.st, find(i.nd)});
if (adj[b].size() > adj[a].size()) adj[a].swap(adj[b]);
for (auto i : adj[b]) adj[a].insert(i);
if (rev_adj[b].size() > rev_adj[a].size()) rev_adj[a].swap(rev_adj[b]);
for (auto i : rev_adj[b]) rev_adj[a].insert(i);
for (int i = 0; i < M; i++){
if (keys[a][i] == 0) continue;
auto it = edges[a].lower_bound({i, 0});
while (it != edges[a].end() && it->st == i){
pii tmp = *it;
tmp.nd = find(tmp.nd);
adj[a].insert(tmp.nd);
rev_adj[tmp.nd].insert(a);
it = edges[a].erase(it);
}
}
}
stack<int> s;
void dfs1(int node){
vis[node] = 1;
set<int> nw;
for (auto i : adj[node]){
int to = find(i);
nw.insert(to);
if (vis[to]) continue;
dfs1(to);
}
s.push(node);
adj[node] = nw;
}
void dfs2(int node, vector<int> &tmp){
set<int> nw;
vis2[node] = 1;
for (auto i : rev_adj[node]){
int to = find(i);
nw.insert(to);
if (vis2[to]) continue;
dfs2(to, tmp);
}
rev_adj[node] = nw;
tmp.pb(node);
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
for (int i = 0; i < n; i++){
par[i] = i, sz[i] = 1;
keys[i][r[i]] = 1;
adj[i].clear(), edges[i].clear(), rev_adj[i].clear();
}
for (int i = 0; i < m; i++){
edges[u[i]].insert({c[i], v[i]});
edges[v[i]].insert({c[i], u[i]});
}
for (int i = 0; i < n; i++){
vector<pii> del;
for (auto j : edges[i]){
if (j.st == r[i]){
adj[i].insert(j.nd);
rev_adj[j.nd].insert(i);
del.pb(j);
}
}
for (auto j : del) edges[i].erase(j);
}
SIZE = n;
int steps = 0;
while(true){
int prv = SIZE;
for (int i = 0; i < n; i++)
vis[i] = 0, vis2[i] = 0;
for (int i = 0; i < n; i++){
if (vis[i] == 0 && par[i] == i) dfs1(i);
}
while(!s.empty()){
int top = s.top();
s.pop();
if (vis2[top]) continue;
vector<int> tmp;
dfs2(top, tomerge[top]);
}
for (int i = 0; i < n; i++){
for (auto j : tomerge[i]) uni(i, j);
tomerge[i].clear();
}
if (prv == SIZE) break;
}
queue<int> q;
for (int i = 0; i < n; i++){
if (par[i] != i) continue;
set<int> tmp;
for (auto j : adj[i]) tmp.insert(find(j));
tmp.erase(i);
adj[i] = tmp;
tmp.clear();
for (auto j : rev_adj[i]) tmp.insert(find(j));
tmp.erase(i);
rev_adj[i] = tmp;
}
for (int i = 0; i < n; i++)
if (par[i] == i && adj[i].empty()) q.push(i);
while(!q.empty()){
int top = q.front();
q.pop();
for (auto i : rev_adj[top]){
sz[i] += sz[top];
adj[i].erase(top);
if (adj[i].empty()) q.push(i);
}
}
vector<int> ans(r.size(), 0);
int mini = n;
for (int i = 0; i < n; i++) mini = min(mini, sz[find(i)]);
for (int i = 0; i < n; i++) if (sz[find(i)] == mini) ans[i] = 1;
return ans;
}
/*
int main() {
fileio();
int n, m;
assert(2 == scanf("%d%d", &n, &m));
std::vector<int> r(n), u(m), v(m), c(m);
for(int i=0; i<n; i++) {
assert(1 == scanf("%d", &r[i]));
}
for(int i=0; i<m; i++) {
assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
}
fclose(stdin);
std::vector<int> ans = find_reachable(r, u, v, c);
for (int i = 0; i < (int) ans.size(); ++i) {
if(i) putchar(' ');
putchar(ans[i]+'0');
}
printf("\n");
return 0;
}
*/
