#include "keys.h"
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ar array
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
const ll INF = 2e18;
struct EzArray {
vector<int> a;
int n;
int T;
EzArray(int sz = 0) : n(sz), T(1), a() {
a.resize(n);
}
void upd(int x) {
a[x] = T;
}
void clear() {
T++;
}
int get(int i) {
return a[i] == T;
}
vi get() {
rep(i, n) a[i] = (a[i] == T);
return a;
}
};
vi find_reachable(vi r, vi U, vi V, vi c) {
int n = r.size();
int m = U.size();
vector<vi> g(n);
bool ok = false;
rep(i, m) {
g[U[i]].push_back(i);
g[V[i]].push_back(i);
}
EzArray ans(n);
int ANS = n + 1;
auto get_size = [&] (int start) {
vi was(n);
vector<vector<int>> to(n);
queue<int> q;
q.push(start);
vi used(n);
used[start] = 1;
int answer = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
answer++;
if (!was[r[v]]) {
was[r[v]] = 1;
for(auto u : to[r[v]]) {
if (!used[u]) {
used[u] = 1;
q.push(u);
}
}
}
for(auto i : g[v]) {
int u = U[i] ^ V[i] ^ v;
if (used[u]) continue;
if (was[c[i]]) {
q.push(u);
used[u] = 1;
} else {
to[c[i]].push_back(u);
}
}
}
if (ANS > answer) {
ANS = answer;
ans.clear();
}
if (ANS == answer) {
rep(i, n) if (used[i]) ans.upd(i);
}
return answer;
};
vi comp(n);
iota(all(comp), 0);
int sz = n;
vector<vi> toc(n);
rep(i, n) toc[i].push_back(i);
EzArray have_col(n);
int K = sqrt(n);
vi ban(n);
while(sz > 0) {
vvi g2(sz), gr2(sz);
vi ban2(sz);
rep(v, sz) {
have_col.clear();
for(auto i : toc[v]) have_col.upd(r[i]);
for(auto i : toc[v]) {
for(auto edge : g[i]) {
int j = U[edge] ^ V[edge] ^ i;
if (!have_col.get(c[edge])) continue;
if (ban[j]) {
ban2[v] = 1;
continue;
}
if (comp[j] == comp[i]) continue;
g2[comp[i]].push_back(comp[j]);
gr2[comp[j]].push_back(comp[i]);
}
}
if (toc[v].size() > ANS || ban2[v]) {
ban2[v] = 1;
continue;
}
if (g2[v].empty()) {
ban2[v] = 1;
if (toc[v].size() < ANS) {
ans.clear();
ANS = toc[v].size();
}
for(auto i : toc[v]) ans.upd(i);
}
}
vi used(sz);
vi ts;
function<void(int)> dfs1 = [&] (int v) {
used[v] = 1;
for(auto u : gr2[v]) {
if (used[u]) continue;
dfs1(u);
}
ts.push_back(v);
};
function<void(int)> dfs_ban = [&] (int v) {
ban2[v] = 1;
for(auto u : gr2[v]) {
if (ban2[u] == 1) continue;
dfs_ban(u);
}
};
rep(i, sz) {
if (ban2[i]) {
dfs_ban(i);
}
}
rep(i, sz) {
if (ban2[i]) {
used[i] = 1;
for(auto j : toc[i]) ban[j] = 1;
}
}
rep(i, sz) {
if (used[i]) continue;
dfs1(i);
}
vi comp2(sz, -1);
//vi cnt(sz, 0);
reverse(all(ts));
function<void(int)> dfs2 = [&] (int v) {
//cnt[comp2[v]]++;
for(auto u : g2[v]) {
if (comp2[u] != -1) continue;
comp2[u] = comp2[v];
dfs2(u);
}
};
int C = 0;
for(auto v : ts) {
if (comp2[v] != -1) continue;
assert(!ban2[v]);
comp2[v] = C++;
dfs2(v);
}
function<void(int)> dfs3 = [&] (int v) {
used[v] = 2;
for(auto u : gr2[v]) {
if (used[u] == 2) continue;
dfs3(u);
}
};
if (sz - C <= K) {
int csz = 0;
for(auto v : ts) {
if (used[v] == 2) continue;
dfs3(v);
assert(!ban2[v]);
int f = toc[v][0];
get_size(f);
csz++;
}
assert(csz <= sz - C);
break;
}
vvi toc2(C);
for(auto v : ts) {
for(auto i : toc[v]) {
toc2[comp2[v]].push_back(i);
comp[i] = comp2[v];
}
}
swap(toc, toc2);
// cerr << sz << ' ' << C << '\n';
sz = C;
// cerr << '\n';
// rep(i, n) cerr << ban[i] << ' ' << comp[i] << '\n';
// cerr << '\n';
}
// cerr << ANS << '\n';
return ans.get();
}
/*
int main() {
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;
}*/
