/**
* @date 2023-05-27 16:46:26
* RAmen!
*/
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define ll long long
using namespace std;
int n, key[300005], spe[300005], iss[300005], fa[300005];
vector<int> comp[300005];
vector<pii> g[300005];
vector<int> col[300005];
bool vis[300005], visc[300005];
vector<int> cl, clc;
int ans; vector<int> out;
int fnd(int x) {
return x == fa[x] ? x : fa[x] = fnd(fa[x]);
}
void clean() {
for(auto u : cl) vis[u] = 0;
for(auto x : clc) {col[x].clear(); visc[x] = 0;} clc.clear();
}
pii bfs(int s) {
queue<int> q; q.push(s); int num = 1;
cl.pb(s); clc.pb(key[s]); vis[s] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
// cout << s << " " << u << endl;
if(fnd(u) != fnd(s)) {
clean(); return mp(fnd(u), num);
}
for(auto v : col[key[u]]) if(!vis[v]) {
vis[v] = 1; num++; cl.pb(v); q.push(v);
}
col[key[u]].clear(); visc[key[u]] = 1;
for(auto now : g[u]) if(!vis[now.fi]) {
if(visc[now.se]) {
vis[now.fi] = 1; num++; cl.pb(now.fi); q.push(now.fi);
}
else {
clc.pb(now.se); col[now.se].pb(now.fi);
}
}
}
clean(); return mp(-1, num);
}
void merge(int a, int b) {
if(b == -1 || spe[b] == -1) {
iss[spe[a]] = 0; spe[a] = -1;
return;
}
if(comp[a].size() > comp[b].size()) {
comp[a].insert(comp[a].end(), comp[b].begin(), comp[b].end());
comp[b].clear();
iss[spe[a]] = 0; spe[a] = spe[b]; fa[b] = a;
}
else {
comp[b].insert(comp[b].end(), comp[a].begin(), comp[a].end());
comp[a].clear();
iss[spe[a]] = 0; fa[a] = b;
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
for(auto x : r) key[++n] = x + 1;
for(int i = 0; i < (int)u.size(); i++) {
u[i]++; v[i]++; c[i]++;
g[u[i]].pb(mp(v[i], c[i])); g[v[i]].pb(mp(u[i], c[i]));
}
/*int m; cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> key[i]; key[i]++;
}
for(int i = 1; i <= m; i++) {
int u, v, c; cin >> u >> v >> c;
u++; v++; c++;
g[u].pb(mp(v, c)); g[v].pb(mp(u, c));
}*/
for(int i = 1; i <= n; i++) {
fa[i] = i; iss[i] = 1; spe[i] = i; comp[i].pb(i);
}
ans = 1e9;
for(int t = 0; t < 25; t++) {
for(int i = 1; i <= n; i++) if(iss[i]) {
pii res = bfs(i);
if(res.fi == -1) {
if(ans > res.se) {
ans = res.se; out = cl;
}
else if(ans == res.se)
out.insert(out.end(), cl.begin(), cl.end());
}
cl.clear();
merge(fnd(i), res.fi);
}
}
vector<int> ret;
for(int i = 1; i <= n; i++)
ret.pb(0);
for(auto x : out) {
ret[x - 1] = 1;
}
return ret;
}
