#include <bits/stdc++.h>
#include "keys.h"
#define pb push_back
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N = 5e3 + 100;
const ll oo = 1e9;
int col[N];
bool mrk[N];
vector <pair<int, int> > a[N];
vector <int> ps[N];
std::vector<int> find_reachable (std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
int m = u.size();
for (int i = 0; i < n; i++) col[i] = r[i];
for (int i = 0; i < m; i++)
{
a[u[i]].pb({v[i], c[i]});
a[v[i]].pb({u[i], c[i]});
}
vector <int> ans;
int mx = oo;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) mrk[j] = 0, ps[j].clear();
set<int> st;
queue <int> q;
q.push(i);
mrk[i] = 1;
int kol = 0;
while (!q.empty())
{
int x = q.front();
q.pop();
if (!st.count(col[x]))
{
for (auto i : ps[col[x]])
if (!mrk[i])
{
q.push(i);
mrk[i] = 1;
}
}
st.insert(col[x]);
kol++;
for (auto i : a[x])
if (!mrk[i.f])
{
if (st.count(i.s))
{
mrk[i.f] = 1;
q.push(i.f);
}
else ps[i.s].pb(i.f);
}
}
if (kol < mx)
{
mx = kol;
ans.clear();
}
if (mx == kol) ans.pb(i);
}
vector <int> ans1(n, 0);
for (auto i : ans) ans1[i] = 1;
return ans1;
}
//
//int main()
//{
// ios_base::sync_with_stdio(0);
// iostream::sync_with_stdio(0);
// cin.tie(0);
// int n, m;
// cin >> n >> m;
// vector <int> r(n);
// vector <int> u(m), v(m), c(m);
// for (int i = 0; i < n; i++) cin >> r[i];
// for (int i = 0; i < m; i++) cin >> u[i] >> v[i] >> c[i];
// vector <int> ans = find_reachable(r, u, v, c);
// for (auto i : ans) cout << i << " ";
// cout << endl;
//}
