#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (false) cerr
using namespace std;
using ll = long long;
const int MAXN = 6e5+10;
int N, M;
vector<int> R, ans, ds;
unordered_map<int, vector<int>> adj[MAXN];
unordered_set<int> keys[MAXN];
vector<int> toVisit[MAXN];
vector<int> vis, finalNodes;
void init() {
rep(i, 0, N) ds[i] = -1;
}
int find(int x) {
if (ds[x] < 0) return x;
int r = find(ds[x]);
ds[x] = r;
return r;
}
void addVisit(unordered_map<int, vector<int>>& a, unordered_set<int>& k, vector<int>& v) {
vector<int> temp;
if (sz(a) < sz(k)) {
// Iterate through edges
for (auto& r : a) {
if (k.count(r.first)) {
// Key and edges match
temp.push_back(r.first);
for (int e : r.second) {
v.push_back(find(e));
}
}
}
} else {
// Iterate through keys
for (auto& r : k) {
if (a.count(r)) {
// Key and edges match
temp.push_back(r);
for (int e : a[r]) {
v.push_back(find(e));
}
}
}
}
for (int r : temp) a.erase(r);
}
int merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return a;
else if (ds[a] < ds[b]) swap(a, b);
auto adjA = adj[a];
auto adjB = adj[b];
auto keysA = keys[a];
auto keysB = keys[b];
auto toVisitA = toVisit[a];
auto toVisitB = toVisit[b];
// Add to toVisit
addVisit(adjA, keysB, toVisitA);
addVisit(adjB, keysA, toVisitB);
// Merge adj, keys, and toVisit
if (sz(adjA) < sz(adjB)) {
adjB.insert(all(adjA));
adj[b] = adjB;
} else {
adjA.insert(all(adjB));
adj[b] = adjA;
}
if (sz(keysA) < sz(keysB)) {
keysB.insert(all(keysA));
keys[b] = keysB;
} else {
keysA.insert(all(keysB));
keys[b] = keysA;
}
if (sz(toVisitA) < sz(toVisitB)) {
toVisitB.insert(toVisitB.end(), all(toVisitA));
toVisit[b] = toVisitB;
} else {
toVisitA.insert(toVisitA.end(), all(toVisitB));
toVisit[b] = toVisitA;
}
// Merge a into b
vis[a] = -1;
vis[b] = 1;
ds[b] += ds[a];
ds[a] = b;
return b;
}
void dfs(int n) {
n = find(n);
if (vis[n] == 2) return;
/*
debug << "dfs(" << n << ")" << endl;
rep(i, 0, N) debug << ds[i] << " \n"[i==N-1];
rep(i, 0, N) {
debug << i << ": ";
for (int k : keys[i]) debug << k << " ";
for (auto r : adj[i]) {
debug << "(" << r.first << " |";
for (int e : r.second) debug << " " << e;
debug << ") ";
}
debug << "/ ";
for (int e : toVisit[i]) debug << e << " ";
debug << endl;
}
debug << endl;
*/
vis[n] = 1;
bool isLeaf = true;
while (!toVisit[n].empty()) {
int e = find(toVisit[n].back());
toVisit[n].pop_back();
// debug << "vis " << e << " from " << n << endl;
if (e == n) continue;
else if (vis[e] == 0) {
// Fresh node; start there
isLeaf = false;
dfs(e);
} else if (vis[e] == 1) {
// Cycle; merge e with this node
isLeaf = false;
int newN = merge(e, n);
dfs(newN);
return;
} else if (vis[e] == 2) {
// Would visit
isLeaf = false;
}
n = find(n);
}
if (isLeaf) finalNodes.push_back(n);
vis[n] = 2;
}
void solve() {
// Generate initial toVisit
rep(n, 0, N) {
keys[n].insert(R[n]);
if (!adj[n].count(R[n])) continue;
for (int e : adj[n][R[n]]) {
toVisit[n].push_back(e);
}
adj[n].erase(R[n]);
}
int minSize = MAXN;
unordered_set<int> minRoots;
rep(n, 0, N) {
if (vis[find(n)] == 0) {
dfs(find(n));
for (int x : finalNodes) {
int s = -ds[x];
if (s < minSize) {
minRoots.clear();
minSize = s;
}
if (s <= minSize) minRoots.insert(x);
}
finalNodes.clear();
}
}
rep(n, 0, N) {
ans[n] = minRoots.count(find(n));
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
N = sz(r), M = sz(u);
R = r;
ans.resize(N);
vis.resize(N);
ds.resize(N);
init();
rep(i, 0, M) {
adj[u[i]][c[i]].push_back(v[i]);
adj[v[i]][c[i]].push_back(u[i]);
}
solve();
return ans;
}
/*
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector<int> r{0,1,1,2};
vector<int> u{0,0,1,1,3};
vector<int> v{1,2,2,3,1};
vector<int> c{0,0,1,0,2};
vector<int> ans = find_reachable(r,u,v,c);
rep(i, 0, sz(ans)) cout << ans[i] << " \n"[i==sz(ans)-1];
return 0;
}
*/
