#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, q, k, x, y, a, b, c;
vector< pair<ll, ll> > G[300000];
vector<int> key;
int rch(ll x) {
map< ll, vector<ll> > mp1, mp2;
set<ll> has;
vector<bool> used(n);
ll ans = 1;
has.insert(key[x]);
used[x] = 1;
for (auto i : G[x]) {
// if (x == 3) {
// cout << i.first << ' ' << i.second << '\n';
// }
if (used[i.first]) {
continue;
}
if (has.count(i.second)) {
mp1[i.second].push_back(i.first);
}
else {
mp2[i.second].push_back(i.first);
}
}
while (!mp1.empty()) {
ans++;
ll x = (*mp1.begin()).second[(*mp1.begin()).second.size() - 1];
(*mp1.begin()).second.pop_back();
if ((*mp1.begin()).second.empty()) {
mp1.erase((*mp1.begin()).first);
}
if (used[x]) {
continue;
}
used[x] = 1;
if (!has.count(key[x]) && mp2.count(key[x])) {
mp1[key[x]] = mp2[key[x]];
mp2.erase(key[x]);
}
has.insert(key[x]);
for (auto i : G[x]) {
if (used[i.first]) {
continue;
}
if (has.count(i.second)) {
mp1[i.second].push_back(i.first);
}
else {
mp2[i.second].push_back(i.first);
}
}
}
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
m = c.size();
key = r;
for (int i = 0; i < m; i++) {
G[u[i]].push_back({v[i], c[i]});
G[v[i]].push_back({u[i], c[i]});
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = rch(i);
}
int mn = *min_element(ans.begin(), ans.end());
for (int i = 0; i < n; i++) {
if (ans[i] == mn) {
ans[i] = 1;
}
else {
ans[i] = 0;
}
}
return ans;
}
