#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)3e5 + 5;
vector<set<int>>keys(mxN);
vector<vector<int>>component(mxN);
set<pair<int,int>>original_adj[mxN];
vector<int>build_adj[mxN];
vector<int>rev_build_adj[mxN];
// SCC
int comp;
bool SCC_vis[mxN];
bool COLOR_vis[mxN];
vector<int>SCC_list;
vector<int>final_color(mxN);
void SCC_dfs(int u) {
SCC_vis[u] = 1;
SCC_list.push_back(u);
for(auto z : build_adj[u]) if(!SCC_vis[z]) {
SCC_dfs(z);
}
}
int current_color;
void SCC_color(int u) {
COLOR_vis[u] = 1;
final_color[u] = current_color;
component[current_color].push_back(u);
for(auto z : rev_build_adj[u]) if(!COLOR_vis[z]) {
SCC_color(z);
}
}
void SCC(int N) {
for(int i = 0 ; i < N ; i++) {
component[i].clear();
keys[i].clear();
}
comp = 0;
memset(SCC_vis, 0, sizeof(SCC_vis));
memset(COLOR_vis, 0, sizeof(COLOR_vis));
SCC_list.clear();
for(int i = 0 ; i < N ; i++) if(!SCC_vis[i]) {
SCC_dfs(i);
}
current_color = 0;
for(auto z : SCC_list) if(!COLOR_vis[z]) {
comp++;
SCC_color(z);
current_color++;
}
}
bool vis[mxN];
int sz;
bool dfs(int u, int col) {
if(final_color[u] != col)
return 0;
vis[u] = 1;
bool ok = 1;
sz++;
for(auto z : build_adj[u]) if(!vis[z]) {
ok &= dfs(z, col);
}
return ok;
}
vector<int>find_reachable(vector<int>r, vector<int>u, vector<int>v, vector<int>c) {
const int n = (int)r.size();
const int m = (int)u.size();
comp = n;
// for each component:
// merge all keys
// iterate over neighbours and add edges when possible
// init
for(int i = 0 ; i < m ; i++) {
original_adj[u[i]].insert({v[i], c[i]});
original_adj[v[i]].insert({u[i], c[i]});
}
for(int i = 0 ; i < n ; i++) {
component[i].push_back(i);
}
for(int i_ = 0 ; i_ < log2(n) ; i_++) {
for(int i = 0 ; i < comp ; i++) { // change to number of comps
for(auto z : component[i]) {
keys[i].insert(r[z]);
//cout << i_ << ' ' << i << ' ' << z << '\n';
}
for(auto z : component[i]) {
vector<pair<int,int>>del;
for(auto e = original_adj[z].begin() ; e != original_adj[z].end() ; e++) {
if(keys[i].find(e->second) != keys[i].end()) {
//if(!i_) cout << "Added edge " << z << ' ' << e.first << '\n';
build_adj[z].push_back(e->first);
rev_build_adj[e->first].push_back(z);
del.push_back(*e);
}
}
for(auto d : del)
original_adj[z].erase(original_adj[z].find(d));
}
}
SCC(n);
}
int mn = INT_MAX;
vector<int>answer(n,0);
for(int i = 0 ; i < comp ; i++) { // change to nr of comps
sz = 0;
if(dfs(component[i][0], i)) {
if(sz == mn) {
for(auto z : component[i])
answer[z] = 1;
} else if(sz < mn) {
mn = sz;
answer.clear();
answer.resize(n,0);
for(auto z : component[i])
answer[z] = 1;
}
}
}
return answer;
}
