#include <vector>
#include "keys.h"
#define F first
#define S second
using namespace std;
const int N = 3e5 + 10;
int n , m , col[N] , root[N] , nex[N] , p[N] , mn;
bool solved[N] , marked[N] , key[N] , vis[N];
vector <int> all_roots;
vector <int> can , cand , ans;
vector <int> to[N];
vector <pair<int ,int>> adj[N];
void Add_vert(int v)
{
for(auto u : adj[v])
{
if(key[u.F])
can.push_back(u.S);
else
to[u.F].push_back(u.S);
}
}
void Add_col(int v)
{
for(auto u : to[v])
can.push_back(u);
to[v].clear();
}
void Find_nex(int star)
{
nex[star] = -1;
vector <int> all;
vector <int> tmp;
all.push_back(star);
marked[star] = true;
while(!all.empty())
{
int v = all.back(); all.pop_back();
if(root[v] != root[star])
{
nex[star] = root[v];
marked[v] = false;
break;
}
tmp.push_back(v);
key[col[v]] = true;
Add_vert(v);
Add_col(col[v]);
while(!can.empty())
{
int u = can.back(); can.pop_back();
if(marked[u])
continue;
marked[u] = true;
all.push_back(u);
}
}
can.clear();
for(auto u : tmp)
{
key[col[u]] = false;
marked[u] = false;
for(auto v : adj[u])
to[v.F].clear();
}
for(auto u : all)
marked[u] = false;
}
void Solve(int star , bool keep = false)
{
vector <int> all , tmp;
all.push_back(star);
marked[star] = true;
while(!all.empty())
{
int v = all.back(); all.pop_back();
key[col[v]] = true;
tmp.push_back(v);
Add_vert(v);
Add_col(col[v]);
while(!can.empty())
{
int u = can.back(); can.pop_back();
if(!marked[u])
{
marked[u] = true;
all.push_back(u);
}
}
}
can.clear();
for(auto u : tmp)
{
key[col[u]] = false;
marked[u] = false;
for(auto v : adj[u])
to[v.F].clear();
if(keep)
ans[u] = 1;
}
p[star] = tmp.size();
}
void Find_root(int v)
{
vis[v] = true;
if(nex[v] == -1)
{
root[v] = -1;
marked[v] = true;
return;
}
if(vis[nex[v]] == true)
{
root[v] = root[nex[v]];
marked[v] = true;
return;
}
Find_root(nex[v]);
root[v] = root[nex[v]];
marked[v] = true;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
m = u.size();
ans.resize(n , 0);
mn = N;
for(int i = 0 ; i < n ; i++)
{
all_roots.push_back(i);
col[i] = r[i];
root[i] = i;
}
for(int i = 0 ; i < m ; i++)
{
adj[u[i]].push_back(make_pair(c[i] , v[i]));
adj[v[i]].push_back(make_pair(c[i] , u[i]));
}
while(!all_roots.empty())
{
for(auto u : all_roots)
Find_nex(u);
for(auto u : all_roots)
{
if(nex[u] == -1)
{
Solve(u);
if(p[u] == mn)
cand.push_back(u);
if(p[u] < mn)
{
cand.clear();
cand.push_back(u);
mn = p[u];
}
solved[u] = true;
}
}
for(auto u : all_roots) if(!marked[u])
Find_root(u);
for(auto u : all_roots)
vis[u] = marked[u] = false;
vector <int> tmp;
for(auto u : all_roots) if(root[u] == u)
tmp.push_back(u);
all_roots = tmp;
}
for(auto u : cand)
Solve(u , 1);
return ans;
}
