#include <vector>
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 999'999;
vector<int> uf;
int find_one_room(int start, vector<int> (&r), vector<vector<pii>> (&edges))
{
int key = r[start];
for (pii x: edges[start])
{
if (x.second == key)
return x.first;
}
return -1;
}
void init_uf(vector<int> (&directed))
{
//cout << "yolo\n";
int n = directed.size();
uf = vector<int> (n, -1);
for (int node = 0; node<n; node++)
{
if (uf[node]==-1)
{
//cout << "let's do node " << node << '\n';
int curr = node;
vector<int> lis;
while (uf[curr] == -1)
{
uf[curr] = -2;
lis.push_back(curr);
curr = directed[curr];
//cout << "damay na si " << curr << '\n';
}
int rep;
if (uf[curr] == -2)
rep = curr;
else
rep = uf[curr];
for (int i: lis)
uf[i] = rep;
}
}
vector<int> count(n, 0);
for (int node = 0; node<n; node++)
count[uf[node]]--;
for (int node = 0; node<n; node++)
if (count[node]<0)
uf[node] = count[node];
}
int fin(int x)
{
if (uf[x]<0)
return x;
int y = fin(uf[x]);
uf[x] = y;
return y;
}
int onion(int x, int y)
{
//NOTE: Whenever this is called, it MUST be the case that we append x to y!
x = fin(x);
y = fin(y);
uf[y] = uf[x]+uf[y];
uf[x] = y;
return y;
}
vector<int> final_answer;
int traverse(int start, vector<int> (&r), vector<vector<pii>> (&edges), bool save)
{
map<int, bool> has_access;
map<int, vector<int>> will_have_access;
int n = edges.size();
vector<bool> rooms_reached(n, 0);
queue<int> rooms_processed;
int ans = 1;
rooms_reached[start] = 1;
if (save)
final_answer[start] = 1;
rooms_processed.push(start);
while (!rooms_processed.empty())
{
int room = rooms_processed.front();
rooms_processed.pop();
int new_key = r[room];
has_access[new_key] = 1;
for (int neigh: will_have_access[new_key])
{
if (rooms_reached[neigh] == 0)
{
rooms_reached[neigh] = 1;
rooms_processed.push(neigh);
ans++;
if (fin(start) != fin(neigh))
{
return 0-onion(start, neigh);
}
if (save)
final_answer[neigh] = 1;
}
}
will_have_access[new_key] = {};
for (pii x: edges[room])
{
int neigh = x.first;
int required = x.second;
if (rooms_reached[neigh] == 0)
{
if (has_access[required])
{
rooms_reached[neigh] = 1;
rooms_processed.push(neigh);
ans++;
if (fin(start) != fin(neigh))
{
return 0-onion(start, neigh);
}
if (save)
final_answer[neigh] = 1;
}
else
will_have_access[required].push_back(neigh);
}
}
}
return ans;
}
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();
vector<vector<pii>> edges(n);
int m = u.size();
for (int i=0; i<m; i++)
{
int uu = u[i];
int vv = v[i];
int corridor = c[i];
edges[uu].push_back({vv, corridor});
edges[vv].push_back({uu, corridor});
}
bool easy = 0;
vector<int> directed(n);
for (int i=0; i<n; i++)
{
directed[i] = find_one_room(i, r, edges);
if (directed[i] == -1)
easy = 1;
}
if (easy)
{
vector<int> ans(n, 0);
for (int i=0; i<n; i++)
if (directed[i] == -1)
ans[i] = 1;
return ans;
}
//cout << "it's easy\n";
//otherwise, we have a directed graph of n nodes and n edges
init_uf(directed);
priority_queue<pii> ccs;
for (int node = 0; node<n; node++)
if (uf[node] < 0)
ccs.push({uf[node], node});
//cout << "nakaabot dito\n";
vector<int> candidate_sizes(n, INF);
while (!ccs.empty())
{
//cout << "processing candidate\n";
pii x = ccs.top();
ccs.pop();
if (uf[x.second] == x.first)
{
int k = traverse(x.second, r, edges, 0);
if (k<=0)
{
int kabit = 0-k;
kabit = fin(kabit);//precautionary measure
if (candidate_sizes[kabit] == INF)
{
ccs.push({uf[kabit], kabit});
}
//else{ this has already been processed earlier, and it doesn't append elsewhere }
}
else
{
candidate_sizes[x.second] = k;
}
}
//else{ ignore, since that means it has been updated }
}
int mini = INF;
for (int node = 0; node<n; node++)
mini = min(mini, candidate_sizes[node]);
final_answer = vector<int> (n, 0);
for (int node = 0; node<n; node++)
if (candidate_sizes[node] == mini)
traverse(node, r, edges, 1);
return final_answer;
}
