#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int nax = 300 * 1000 + 10, INF = 1e9 + 10;
int n, m;
int type[nax];
map<int, vi>outEdges[nax];
set<int>colors[nax];
set<int>valid[nax];
int par[nax], siz[nax], nxt[nax], par2[nax];
bool done[nax];
queue<int>Q;
int deg[nax];
vi who[nax];
int Fund(int x) {
if(par[x] != x) par[x] = Fund(par[x]);
return par[x];
}
int Fund2(int x) {
x = Fund(x);
if(Fund(par2[x]) != x) par2[x] = Fund(Fund2(Fund(par2[x])));
return Fund(par2[x]);
}
void Onion(int a, int b) {
a = Fund(a), b = Fund(b);
if(a == b) return;
if((int)who[a].size() < (int)who[b].size()) swap(a, b);
for(auto it : outEdges[b]) {
if(colors[a].count(it.ST)) {
for(int x : it.ND) {
valid[a].insert(x);
}
} else {
for(int x : it.ND) {
outEdges[a][it.ST].PB(x);
siz[a]++;
}
}
}
for(int x : valid[b]) {
valid[a].insert(x);
}
for(int x : who[b]) {
who[a].PB(x);
}
for(int x : colors[b]) {
for(int y : outEdges[a][x]) {
valid[a].insert(y);
}
siz[a] -= (int)outEdges[a][x].size();
outEdges[a][x].clear();
colors[a].insert(x);
}
who[b].clear();
colors[b].clear();
valid[b].clear();
outEdges[b].clear();
par[b] = a;
}
void merge(int x) {
x = Fund(x);
int y = x;
while(Fund(nxt[y]) != x) {
y = Fund(nxt[y]);
Onion(y, x);
}
}
vi find_reachable(vi _r, vi _u, vi _v, vi _c) {
n = (int)_r.size();
for(int i = 0; i < n; ++i) {
type[i] = _r[i];
}
m = (int)_u.size();
for(int i = 0; i < m; ++i) {
outEdges[_u[i]][_c[i]].PB(_v[i]);
outEdges[_v[i]][_c[i]].PB(_u[i]);
siz[_u[i]]++;
siz[_v[i]]++;
}
vi emptyOut;
for(int i = 0; i < n; ++i) {
if((int)outEdges[i][type[i]].size() == 0) {
emptyOut.PB(i);
} else {
nxt[i] = outEdges[i][type[i]].back();
deg[nxt[i]]++;
par[i] = i;
who[i] = {i};
par2[i] = nxt[i];
colors[i].insert(type[i]);
for(int x : outEdges[i][type[i]]) {
valid[i].insert(x);
}
siz[i] -= (int)outEdges[i][type[i]].size();
outEdges[i][type[i]].clear();
}
}
if((int)emptyOut.size() > 0) {
vi ans(n);
fill(ans.begin(), ans.end(), 0);
for(int x : emptyOut) ans[x] = 1;
return ans;
}
for(int i = 0; i < n; ++i) {
if(deg[i] == 0) {
Q.push(i);
}
}
while(!Q.empty()) {
int x = Q.front();
Q.pop();
done[x] = true;
deg[nxt[x]]--;
if(deg[nxt[x]] == 0) {
Q.push(nxt[x]);
}
}
//for(int i = 0; i < n; ++i) {
//cerr << nxt[i] << " ";
//}
set<int>roots;
for(int i = 0; i < n; ++i) {
if(!done[i]) {
int x = i;
while(nxt[x] != i) {
x = nxt[x];
Onion(x, i);
done[x] = true;
}
done[i] = true;
merge(i);
roots.insert(i);
}
}
return {1};
//cerr << "gg\n";
vector<vi>reach;
int ans = INF;
while(!roots.empty()) {
int r = *roots.begin();
roots.erase(r);
r = Fund(r);
if(!valid[r].empty()) {
int x = *valid[r].begin();
valid[r].erase(x);
nxt[r] = r;
int x2 = x;
while(Fund(x2) != Fund(nxt[x2])) {
x2 = nxt[x2];
}
nxt[r] = Fund(x);
if(Fund(x2) == r) {
merge(r);
roots.insert(r);
} else {
par2[r] = nxt[r];
}
} else {
// znalazlem nie powiekszalny set
reach.PB(who[r]);
ans = min(ans, (int)who[r].size());
}
}
vi res(n);
fill(res.begin(), res.end(), 0);
for(auto v : reach) {
if(ans != (int)v.size()) continue;
for(int x : v) res[x] = 1;
}
return res;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
//auto p = find_reachable({0, 1, 1, 2, 2, 1, 2},
//{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
//{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
//{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
//for(int x : p) cout << x << " ";
//find_reachable({0, 0, 0}, {0}, {1}, {0});
//}
