#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
typedef long long llong;
const int MAXN = 300000 + 10;
const int INF = 1e9;
int n, m;
int p[MAXN];
int c[MAXN];
bool pushed[MAXN];
bool unlocked[MAXN];
std::queue <int> toUnlock;
std::vector <std::pair <int,int>> g[MAXN];
std::vector <std::pair <int,int>> byColor[MAXN];
std::vector <int> find_reachable(std::vector <int> r, std::vector <int> u, std::vector <int> v, std::vector <int> _col)
{
n = r.size();
m = u.size();
for (int i = 0 ; i < n ; ++i)
{
c[i + 1] = r[i] + 1;
}
for (int i = 0 ; i < m ; ++i)
{
byColor[_col[i] + 1].push_back({u[i] + 1, v[i] + 1});
g[u[i] + 1].push_back({v[i] + 1, _col[i] + 1});
g[v[i] + 1].push_back({u[i] + 1, _col[i] + 1});
}
int min = n;
std::vector <int> sol;
for (int i = 1 ; i <= n ; ++i)
{
std::fill(pushed + 1, pushed + 1 + n, false);
std::fill(unlocked + 1, unlocked + 1 + n, false);
toUnlock.push(i);
pushed[i] = true;
while (toUnlock.size())
{
p[i]++;
int node = toUnlock.front();
toUnlock.pop();
if (!unlocked[c[node]])
{
for (const auto &[from, to] : byColor[c[node]])
{
if (pushed[from] ^ pushed[to])
{
if (pushed[from])
{
toUnlock.push(to);
pushed[to] = true;
} else
{
toUnlock.push(from);
pushed[from] = true;
}
}
}
unlocked[c[node]] = true;
}
for (const auto &[u, col] : g[node])
{
if (!pushed[u] && unlocked[col])
{
pushed[u] = true;
toUnlock.push(u);
}
}
}
min = std::min(min, p[i]);
}
for (int i = 1 ; i <= n ; ++i)
{
if (p[i] == min)
{
sol.push_back(1);
} else
{
sol.push_back(0);
}
}
return sol;
}
