#include <iostream>
#include <queue>
using namespace std;
const int N = 1<<17;
vector<pair<int, int>> nei[N];
vector<int> vec[N];
int Par[N], seenVer[N], seenCol[N], updVec[N], Used[N], day, Day;
int root(int v){
// cout<<v<<endl;
return (Par[v] == 0 or 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 (t == 1)
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);
vec[cl].clear();
}
if (t == 0 and root(u) != i){
Par[i] = root(u);
Used[i] = Day;
break;
}
for (auto [u, c] : nei[u]){
if (seenVer[u] != day and seenCol[c] == day)
Q.push(u), seenVer[u] = day;
else if (seenVer[u] != day){
if (updVec[c] != day)
vec[c].clear(), updVec[c] = day;
vec[c].push_back(u);
}
}
}
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, fxd;
for (int i=0;i<n;i++)
cnd.push_back(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;
Day++;
for (int i : cnd)
Extend(r, i, 0);
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;
}
