#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "keys.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
int n;
int par[N], sz[N];
map <int, vector <int> > g[N];
set <int> key[N];
vector <int> to[N];
int Find(int u) {
return (u == par[u] ? u : par[u] = Find(par[u]));
}
void Union(int u, int v) {
if ((u = Find(u)) == (v = Find(v))) return;
//if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
if (key[u].size() + to[u].size() < key[v].size() + to[v].size()) swap(key[u], key[v]), swap(to[u], to[v]);
for (auto w: to[v]) to[u].push_back(w);
to[v].clear();
for (auto c: key[v]) {
if (g[u].find(c) != g[u].end()) {
for (auto w: g[u][c]) to[u].push_back(w);
g[u].erase(c);
}
}
for (auto [c, _]: g[v]) {
if (key[u].find(c) != key[u].end()) {
for (auto w: g[v][c]) to[u].push_back(w);
} else for (auto w: g[v][c]) g[u][c].push_back(w);
}
g[v].clear();
key[u].insert(key[v].begin(), key[v].end());
key[v].clear();
}
int bad[N];
int state[N];
int last[N];
void dfs(int u) {
state[u] = 0;
while (1) {
u = Find(u);
if (to[u].empty()) break;
int v = to[u].back();
to[u].pop_back();
v = Find(v);
if (u == v) continue;
if (state[v] == -1) {
last[v] = u;
dfs(v);
if (Find(u) != Find(v)) bad[u] = 1;
} else if (state[v] == 0) {
int w = u;
while (1) {
if (Find(w) == Find(v)) break;
Union(v, w);
w = last[w];
}
} else bad[u] = 1;
}
state[u] = 1;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
int m = c.size();
auto add_edge = [&](int u, int v, int c) {
if (r[u] == c) to[u].push_back(v);
else g[u][c].push_back(v);
};
for (int i = 0; i < m; ++i) {
add_edge(u[i], v[i], c[i]);
add_edge(v[i], u[i], c[i]);
}
for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1, key[i].insert(r[i]);
memset(state, -1, sizeof(state));
for (int i = 0; i < n; ++i) if (state[i] == -1) dfs(i);
for (int i = 0; i < n; ++i) if (bad[i]) bad[Find(i)] = 1;
vector <int> flag(n, 0);
int ans = 1e9;
for (int i = 0; i < n; ++i)
if (i == Find(i) && !bad[i]) ans = min(ans, sz[i]);
for (int i = 0; i < n; ++i)
if (!bad[Find(i)] && sz[Find(i)] == ans) flag[i] = 1;
return flag;
}
//int main() {
// freopen("IOI21_keys.inp", "r", stdin);
//// freopen("IOI21_keys.out", "w", stdout);
// 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;
//}
