#include <vector>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <cassert>
using namespace std;
const int MAXN = 3e5 + 123;
vector<pair<int, int>> edg[MAXN];
int keyget[MAXN];
bitset<MAXN> used;
vector<int> component[MAXN];
int rcomponent[MAXN];
vector<int> edg0[MAXN];
vector<int> redg0[MAXN];
void dfs1(int v, vector<int>& rtout){
used[v] = 1;
for(auto u : edg0[v]){
if(used[u])
continue;
dfs1(u, rtout);
}
rtout.push_back(v);
}
void dfs2(int v, vector<int>& compincl){
used[v] = 1;
compincl.push_back(v);
for(auto u : redg0[v]){
if(used[u])
continue;
dfs2(u, compincl);
}
}
void update_edg0(int n, int nstart){
for(int v = 0; v < n; ++v){
edg0[v].clear();
redg0[v].clear();
}
for(int v = 0; v < nstart; ++v){
for(auto [u, c] : edg[v]){
if(rcomponent[u] == rcomponent[v])
continue;
if(keyget[rcomponent[v]] & (1 << c)){
edg0[rcomponent[v]].push_back(rcomponent[u]);
redg0[rcomponent[u]].push_back(rcomponent[v]);
}
}
}
}
int condensate(int n, int nstart){
used.reset();
vector<int> rtout;
for(int i = 0; i < n; ++i){
if(used[i])
continue;
dfs1(i, rtout);
}
used.reset();
vector<vector<int>> newcomponent;
reverse(rtout.begin(), rtout.end());
for(auto v : rtout){
if(used[v])
continue;
newcomponent.push_back({});
dfs2(v, newcomponent.back());
}
int n0 = newcomponent.size();
vector<int> newkeyget(n0, 0);
for(int i = 0; i < n0; ++i){
vector<int>& comp = newcomponent[i];
for(auto v : comp){
newkeyget[i] |= keyget[v];
for(auto v0 : component[v]){
rcomponent[v0] = i;
}
}
}
for(int i = 0; i < n0; ++i){
keyget[i] = newkeyget[i];
component[i].clear();
}
for(int v = 0; v < nstart; ++v)
component[rcomponent[v]].push_back(v);
update_edg0(n, nstart);
return n0;
}
vector<int> solve_small(int n){
int nstart = n;
for(int i = 0; i < n; ++i){
rcomponent[i] = i;
component[i].push_back(i);
}
update_edg0(n, n);
int cnt = 0;
//cout << "BLYAT\n";
while(true){
assert(cnt++ < 35);
int n0 = condensate(n, nstart);
if(n == n0)
break;
n = n0;
}
//cout << "BLYAT\n";
//for(int i = 0; i < n; ++i){
//cout << "---" << i << "---\n";
//for(auto v : component[i]){
//cout << v << ' ';
//}
//cout << '\n' << edg0[i].size() << '\n';
//}
vector<int> ans;
unsigned ansvl = MAXN;
for(int i = 0; i < n; ++i){
if(edg0[i].size())
continue;
if(ansvl > component[i].size()){
ansvl = component[i].size();
ans = component[i];
} else if(ansvl == component[i].size()){
for(auto v : component[i])
ans.push_back(v);
}
}
//cout << ansvl << '\n';
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
int maxr = 0;
for(int i = 0; i < n; ++i){
keyget[i] = r[i];
maxr = max(maxr, r[i]);
}
for(int i = 0; i < m; ++i){
edg[u[i]].push_back({v[i], c[i]});
edg[v[i]].push_back({u[i], c[i]});
maxr = max(maxr, c[i]);
}
//if(n <= 0000 && m <= 2000){
//vector<int> ans = solve_quad(n);
//int mn = *min_element(ans.begin(), ans.end());
//for(int i = 0; i < n; ++i)
//ans[i] = (ans[i] == mn);
//return ans;
//} else if(maxr <= 29){
for(int i = 0; i < n; ++i)
keyget[i] = (1 << keyget[i]);
vector<int> ans = solve_small(n);
vector<int> rans(n, 0);
for(auto v : ans)
rans[v] = 1;
return rans;
//}
}
