#include <vector>
#include <algorithm>
#include <tuple>
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ff first
#define ss second
using namespace std;
int n, N;
const int INF = (int)1e9 + 7;
vector<int> R, C;
vector<vector<int>> gph[303030];
vector<int> edge[303030];
vector<bool> key[303030];
vector<pii> ran;
int ord[303030];
int rev[303030];
int cnt = 0;
int val = 0;
bool dfs(int x)
{
int ret = ord[x] = ++cnt;
rev[cnt] = x;
edge[x].resize(N, INF);
key[x].resize(N, false);
vector<int> Q;
Q.push_back(R[x]);
while(Q.size())
{
int c = Q.back(); Q.pop_back();
if(key[x][c]) continue;
key[x][c] = true;
for(int y : gph[x][c])
{
if(!ord[y])
{
if(dfs(y)) return true;
for(int i = 0; i < N; ++i)
{
edge[x][i] = min(edge[x][i], edge[y][i]);
if(!key[x][i] && key[y][i]) Q.push_back(i);
}
}
else edge[x][c] = min(edge[x][c], ord[y]);
}
}
for(int i = 0; i < N; ++i)
{
if(key[x][i]) ret = min(ret, edge[x][i]);
else for(int y : gph[x][i]) if(!ord[y]) edge[x][i] = min(edge[x][i], ord[y]);
}
if(ret < val) { val = ord[x] + 1; return true; }
if(ret >= ord[x])
{
ran.push_back({ord[x], cnt});
val = ord[x] + 1;
return true;
}
return false;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
n = r.size();
int m = u.size();
N = 0;
for(int i = 0; i < n; ++i) N = max(N, r[i]);
for(int i = 0; i < m; ++i) N = max(N, c[i]);
++N;
for(int i = 0; i < n; ++i) gph[i].resize(N);
R = r, C = c;
for(int i = 0; i < m; ++i)
{
gph[u[i]][c[i]].push_back(v[i]);
gph[v[i]][c[i]].push_back(u[i]);
}
for(int i = 0; i < n; ++i) if(!ord[i]) dfs(i);
int mn = INF;
for(auto [x, y] : ran) mn = min(mn, y - x);
vector<int> ans(n);
for(auto [x, y] : ran) if(mn == y - x)
{
for(int i = x; i <= y; ++i)
ans[rev[i]] = 1;
}
return ans;
}
