#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int>> adj[300300];
int num[300300], INV[300300], L[300300], R[300300], dep[300300], mdep[300300], mnum[300300], col[300300], cnt = 1, rdep[300300];
bool on[300300], leaf[300300];
bool comp(int x, int y){
return dep[x] < dep[y];
}
void dfs(int s, int pa = -1){
//int org = s;
num[s] = cnt; ///renumbering
INV[cnt] = s;
s = num[s];
cnt++;
if (pa!=-1) dep[s] = dep[pa] + 1;
L[s] = s, R[s] = s;
mdep[s] = s, mnum[s] = s;
on[s] = 1, leaf[s] = 1;
for (auto &[v, c]:adj[INV[s]]) if (col[INV[s]] == c){
if (!num[v]){
leaf[s] = 0;
dfs(v, s);
R[s] = R[num[v]];
mdep[s] = min(mdep[s], mdep[num[v]], comp);
mnum[s] = min(mnum[s], mnum[num[v]]);
}
else if (on[num[v]]){
//printf("YES %d -> %d, c = %d\n", org, v, c);
mdep[s] = min(mdep[s], num[v], comp);
}
else if (num[v]<s){
//printf("YES\n");
mnum[s] = min(mnum[s], num[v]);
}
}
//printf(" %d -> %d: %d %d\n", org, s, L[s], R[s]);
on[s] = 0;
}
bool valid(int s){
return mdep[s]==s && mnum[s]==s;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
std::vector<int> ans(r.size());
int n = r.size();
///build graph
for (int i=1;i<=n;i++){
col[i] = r[i-1];
}
for (int i=0;i<(int)u.size();i++){
adj[u[i]+1].emplace_back(v[i]+1, c[i]);
adj[v[i]+1].emplace_back(u[i]+1, c[i]);
}
///
for (int i=1;i<=n;i++) if (!num[i]){
dfs(i);
//printf("%d -> %d: %d %d\n", i, num[i], L[i], R[i]);
}
for (int i=1;i<=n;i++){
//printf("%d: %d\n", i, dep[i]);
if (mdep[i]==i) rdep[i] = i;
else rdep[i] = rdep[mdep[i]];
//printf("%d: %d %d\n", i, mdep[i], rdep[i]);
}
int mx = -1, cans = 1e9;
for (int i=1;i<=n;i++) if (leaf[i] && i>mx){
int Rt = rdep[i];
if (!valid(Rt)) continue;
cans = min(cans, R[Rt]-L[Rt]+1);
}
mx = -1;
for (int i=1;i<=n;i++) if (leaf[i] && i>mx){
int Rt = rdep[i];
if (!valid(Rt) || cans<R[Rt]-L[Rt]+1) continue;
assert(cans==R[Rt]-L[Rt]+1);
//printf("%d: %d %d %d\n", i, L[Rt], R[Rt], cans);
for (int j=L[Rt];j<=R[Rt];j++) ans[INV[j]-1] = 1;
mx = R[Rt];
}
return ans;
}
