#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, i, j, sbt = 5, mc = 0, mr = 0, mi;
vector<vector<pair<int, int> > > w;
vector<int> s;
vector<bool> vi, ky;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
n = r.size();
m = u.size();
w.resize(n);
s.resize(n);
vi.resize(n);
ky.resize(n);
mi = n;
for (i = 0; i < m; i++)
{
w[u[i]].push_back({v[i], c[i]});
w[v[i]].push_back({u[i], c[i]});
mc = max(mc, c[i]);
}
for (i = 0; i < n; i++)
mr = max(mr, r[i]);
if (mc <= 29 && mr <= 29)
sbt = 4;
if (n <= 2000 && m <= 2000)
sbt = 3;
if (n <= 200 && m <= 200)
sbt = 2;
if (sbt == 2)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
vi[j] = ky[j] = false;
vi[i] = ky[r[i]] = true;
queue<int> q;
q.push(i);
s[i] = 0;
while (!q.empty())
{
int t = q.front();
q.pop();
s[i]++;
for (auto k : w[t])
{
if (!vi[k.first] && ky[k.second])
{
q.push(k.first);
vi[k.first] = ky[r[k.first]] = true;
}
}
}
mi = min(mi, s[i]);
}
for (i = 0; i < n; i++)
{
if (s[i] == mi)
s[i] = 1;
else
s[i] = 0;
}
}
return s;
}
