#include <vector>
#include <bits/stdc++.h>
#include "keys.h"
//#include "grader.cpp"
using namespace std;
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
typedef pair<int,int> pii;
vector<pii> muchii[300005];
int use[300005];
int room[300005];
int cnt[300005];
int found[300005];
vector<pii> g[300005];
int seen[300005];
int n,m;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
n=r.size();
m=u.size();
for(int i=0;i<m;i++)
{
int a=u[i],b=v[i],cul=c[i];
muchii[a].push_back({b,cul});
muchii[b].push_back({a,cul});
g[cul].push_back({a,b});
}
vector<int> ans;
for(int i=0;i<n;i++)
{
ans.push_back(0);
room[i]=r[i];
}
int minim=1e9;
for(int i=0;i<n;i++)
{
queue<int> coada;
coada.push(i);
while(!coada.empty())
{
int nod=coada.front();
coada.pop();
if(use[nod]==i+1)
continue;
cnt[i]++;
use[nod]=i+1;
int cul=room[nod];
if(found[cul]!=i+1)
{
found[cul]=i+1;
for(pii p:g[cul])
{
int a=p.first;
int b=p.second;
if(use[a]!=i+1)
swap(a,b);
if(use[a]==i+1&&use[b]!=i+1)
coada.push(b);
}
}
for(pii p:muchii[nod])
{
int a=p.first;
int cc=p.second;
if(found[cc]==i+1)
if(use[a]!=i+1)
coada.push(a);
}
}
minim=min(minim,cnt[i]);
}
for(int i=0;i<n;i++)
if(cnt[i]==minim)
ans[i]=1;
return ans;
}
