#include <iostream>
#include <queue>
using namespace std;
const int N = 3<<17;
vector<pair<int, int>> nei[N], mrg;
vector<int> vec[N];
int Par[N], seenVer[N], seenCol[N], updVec[N], Used[N], Bfs[N], day, Day;
int root(int v){
return (Par[v] == v ? v : Par[v] = root(Par[v]));
}
vector<int> Extend(vector<int> &r, int i, int t){
day++;
queue<int> Q;
Q.push(i);
vector<int> ans;
while (Q.size() > 0){
int u = Q.front(), cl = r[u];
Q.pop();
if (Bfs[u] == day)
continue;
Bfs[u] = day;
ans.push_back(u);
if (seenCol[cl] != day){
seenCol[cl] = day;
if (updVec[cl] != day)
vec[cl].clear(), updVec[cl] = day;
for (int j : vec[cl])
Q.push(j), seenVer[j] = day;
vec[cl].clear();
}
if (root(u) != i)
return mrg.push_back({i, u}), ans;
for (auto [v, c] : nei[u]){
if (seenVer[v] != day and seenCol[c] == day)
Q.push(v), seenVer[v] = day;
else if (seenVer[v] != day){
if (updVec[c] != day)
vec[c].clear(), updVec[c] = day;
vec[c].push_back(v);
}
}
}
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C){
int n = r.size(), m = C.size();
vector<int> cnd(n), fxd;
for (int i=0;i<n;i++)
cnd[i] = Par[i] = i;
for (int i=0;i<m;i++){
nei[U[i]].push_back({V[i], C[i]});
nei[V[i]].push_back({U[i], C[i]});
}
for (; cnd.size() > 0; ){
vector<int> Cnd;
mrg = {};
for (int i : cnd)
Extend(r, i, 0);
for (auto [x, y] : mrg){
if (root(x) != root(y))
Par[root(x)] = root(y), Used[root(y)] = day;
}
for (int i : cnd){
if (i == root(i) and Used[i] == day)
Cnd.push_back(i);
else if (i == root(i))
fxd.push_back(i);
}
swap(Cnd, cnd);
}
vector<int> ans(n, 0);
int vl = 1, mn = n + 1;
for (int i : fxd){
vector<int> lst = Extend(r, i, 1);
if (lst.size() < mn)
mn = lst.size(), vl++;
if (lst.size() == mn){
for (int j : lst)
ans[j] = vl;
}
}
for (int &i : ans)
i /= vl;
return ans;
}
