#include<bits/stdc++.h>
using namespace std;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
const int lim = 3e5 + 5;
int n, m;
vector<int>r, u, v, c, g[lim];
namespace sub1{
vector<int>solve(){
int best_cnt = n + 1, cnt;
vector<int>color(n, 0), ans;
vector<bool>vis(n);
function<void(int)>dfs;
dfs = [&] (int s){
vis[s] = true;
cnt++;
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(!vis[d]){
dfs(d);
}
}
};
for(int i = 0; i < n; i++){
if(r[i] == 0){
cnt = 0;
fill(vis.begin(), vis.end(), false);
dfs(i);
}
else{
cnt = 1;
}
if(minimize(best_cnt, cnt)){
ans.clear();
}
if(best_cnt == cnt){
ans.push_back(i);
}
}
for(int& x : ans){
color[x] = 1;
}
return color;
}
}
namespace sub23{
vector<int>solve(){
vector<vector<int>>vc(n);
vector<int>lab(n), siz(n), ans(n, 0), small;
auto find_set = [&] (int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
};
auto merge = [&] (int i, int j){
if((i = find_set(i)) != (j = find_set(j))){
if(vc[i].size() < vc[j].size()){
swap(i, j);
}
siz[lab[j] = i] += siz[j];
for(int& k : vc[j]){
vc[i].push_back(k);
}
}
};
for(int i = 0, best_cnt = n + 1; i < n; i++){
for(int j = 0; j < n; j++){
siz[lab[j] = j] = 1;
vc[j].clear();
vc[j].push_back(r[j]);
}
vector<vector<int>>ec(n);
for(int j = 0; j < m; j++){
ec[c[j]].push_back(j);
}
while(!vc[find_set(i)].empty()){
int x = vc[find_set(i)].back();
vc[find_set(i)].pop_back();
for(int& k : ec[x]){
merge(u[k], v[k]);
}
ec[x].clear();
}
if(minimize(best_cnt, siz[find_set(i)])){
small.clear();
}
if(best_cnt == siz[find_set(i)]){
small.push_back(i);
}
}
for(int& x : small){
ans[x] = 1;
}
return ans;
}
}
namespace sub4{
vector<int>solve(){
queue<int>q;
for(int i = 0; i < m; i++){
q.push(i);
}
vector<int>mask(n);
for(int i = 0; i < n; i++){
mask[i] = 1 << r[i];
}
auto update_from_to = [&] (int u, int v, int c){
if(mask[u] >> c & 1){
int x = mask[u];
if((mask[u] |= mask[v]) != x){
for(int& i : g[u]){
q.push(i);
}
}
}
};
while(!q.empty()){
int i = q.front();
q.pop();
update_from_to(u[i], v[i], c[i]);
update_from_to(v[i], u[i], c[i]);
}
for(int i = 0; i < n; i++){
g[i].clear();
}
for(int i = 0; i < m; i++){
if(mask[u[i]] >> c[i] & 1){
g[u[i]].push_back(v[i]);
}
if(mask[v[i]] >> c[i] & 1){
g[v[i]].push_back(u[i]);
}
}
vector<int>color(n), low(n), num(n, 0), stk, siz;
vector<bool>out(n, false);
int tdfs = 0, cnt_color = 0;
function<void(int)>dfs;
dfs = [&] (int s){
stk.push_back(s);
low[s] = num[s] = ++tdfs;
for(int& d : g[s]){
if(!out[d]){
if(num[d] == 0){
dfs(d);
minimize(low[s], low[d]);
}
else{
minimize(low[s], num[d]);
}
}
}
if(low[s] == num[s]){
int siz_color = 0;
while(true){
int x = stk.back();
stk.pop_back();
color[x] = cnt_color;
out[x] = true;
siz_color++;
if(x == s){
break;
}
}
siz.push_back(siz_color);
cnt_color++;
}
};
for(int i = 0; i < n; i++){
if(num[i] == 0){
dfs(i);
}
}
vector<bool>avai(cnt_color, true), best_col(cnt_color, false);
for(int i = 0; i < n; i++){
for(int& j : g[i]){
if(color[i] != color[j]){
avai[color[i]] = false;
}
}
}
vector<int>cand_col;
for(int i = 0, best_cnt = n + 1; i < cnt_color; i++){
if(avai[i]){
if(minimize(best_cnt, siz[i])){
cand_col.clear();
}
if(best_cnt == siz[i]){
cand_col.push_back(i);
}
}
}
for(int& x : cand_col){
best_col[x] = true;
}
vector<int>ans(n, 0);
for(int i = 0; i < n; i++){
if(best_col[color[i]]){
ans[i] = 1;
}
}
return ans;
}
}
namespace sub5{
int best_size = lim, lab[lim];
bitset<lim>can_color, vis, no_merge;
vector<int>ans, ver_at_col[lim];
int find_set(int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
}
void bfs(int root){
queue<int>q;
q.push(root);
bool flag = false;
vector<int>vertex, remain, in_color;
while(!q.empty()){
int s = q.front();
q.pop();
if(find_set(s) != root){
vis[lab[root] = find_set(s)] = flag = true;
break;
}
if(!vis[s]){
vertex.push_back(s);
vis[s] = can_color[r[s]] = true;
in_color.push_back(r[s]);
for(int& x : ver_at_col[r[s]]){
q.push(x);
}
ver_at_col[r[s]].clear();
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(can_color[c[i]]){
q.push(d);
}
else{
ver_at_col[c[i]].push_back(d);
remain.push_back(c[i]);
}
}
}
}
for(int& x : in_color){
can_color[x] = false;
}
for(int& x : remain){
ver_at_col[x].clear();
}
if(!flag){
if(minimize(best_size, int(vertex.size()))){
ans.clear();
}
if(best_size == vertex.size()){
for(int& i : vertex){
ans.push_back(i);
}
}
no_merge[root] = true;
}
}
vector<int>solve(){
iota(lab, lab + n, 0);
can_color.reset();
vis.reset();
no_merge.reset();
while(true){
bool need = true;
vis.reset();
for(int i = 0; i < n; i++){
if(!no_merge[i] && !vis[i] && find_set(i) == i){
bfs(i);
need = false;
}
}
if(need){
break;
}
}
vector<int>color(n, 0);
for(int& i : ans){
color[i] = 1;
}
return color;
}
}
vector<int>find_reachable(vector<int>_r, vector<int>_u, vector<int>_v, vector<int>_c){
swap(r, _r);
swap(u, _u);
swap(v, _v);
swap(c, _c);
m = u.size();
for(int i = 0; i < m; i++){
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
if(max(n = r.size(), m) <= 200 && *max_element(c.begin(), c.end()) == 0){
return sub1::solve();
}
if(max(n, m) <= 2000){
return sub23::solve();
}
if(max(*max_element(r.begin(), r.end()), *max_element(c.begin(), c.end())) <= 29){
return sub4::solve();
}
return sub5::solve();
}
