#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef set<int> si;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define ALL(x) begin(x), end(x)
#define sz(x) (int)x.size()
vi find_reachable(vi r, vi u, vi v, vi c)
{
int n = sz(r);
int m = sz(c);
vvii adj(n);
loop(m, i)
{
adj[u[i]].pb({v[i], c[i]});
adj[v[i]].pb({u[i], c[i]});
}
int min = n;
auto firstReachable = [&](int i) -> int
{
int key = r[i];
for (auto [j, keyNeeded] : adj[i])
{
if (keyNeeded == key)
{
return j;
}
}
return -1;
};
vi next(n);
vi ans(n);
loop(n, i)
{
int j = firstReachable(i);
if (j == -1)
{
min = 1;
ans[i] = 1;
}
else
next[i] = j;
}
if (min == 1)
return ans;
vi cycles;
vi vis(n, -1);
auto dfs = [&](auto &&self, int i, int l, int iter) -> void
{
vis[i] = iter;
int j = next[i];
if (vis[j] == -1)
self(self, j, l + 1, iter);
else if (vis[j] == iter)
{
if (l + 1 < min)
{
min = l + 1;
cycles = {i};
}
else if (l + 1 == min)
{
cycles.pb(i);
}
}
};
loop(n, i)
{
if (vis[i] == -1)
dfs(dfs, i, 0, i);
}
auto dfs2 = [&](auto &&self, int i) -> void
{
ans[i] = 1;
int j = next[i];
if (!ans[j])
self(self, j);
};
for (int i : cycles)
dfs2(dfs2, i);
return ans;
}
