#include <bits/stdc++.h>
using namespace std;
#define maxn 300010
struct node{
int id, sz, par, is_deactivated;
vector <int> keys;
vector <int> rooms;
vector < pair<int,int> > edges; // pairs (key, room)
};
int print_flag;
vector <int> key_store[maxn], room_store[maxn];
vector < pair<int,int> > edge_store[maxn];
int sz[maxn], node_par[maxn], id[maxn];
int par[maxn], ans[maxn], is_deactivated[maxn];
int root (int v){
if (v==par[v]) return v;
return par[v]= root(par[v]);
}
void merge (int i, int j){
i= root(i);
j= root(j);
if (i==j) return;
if (sz[i]>sz[j]) {
par[j]=i;
for (int key:key_store[j]) key_store[i].push_back(key);
for (pair <int,int> p:edge_store[j]) edge_store[i].push_back(p);
for (int room:room_store[j]) room_store[i].push_back(room);
key_store[j].clear();
edge_store[j].clear();
room_store[j].clear();
sz[i] += sz[j];
}
else{
par[i]=j;
for (int key:key_store[i]) key_store[j].push_back(key);
for (pair<int, int> p:edge_store[i]) edge_store[j].push_back(p);
for (int room:room_store[i]) room_store[j].push_back(room);
key_store[i].clear();
edge_store[i].clear();
room_store[i].clear();
sz[j] += sz[i];
}
}
vector <int> adj[maxn], rev_adj[maxn], extended_adj[maxn];
int key_is_available[maxn];
void add_edges (int n){
for (int i=1; i<=n; i++) {
adj[i].clear();
extended_adj[i].clear();
rev_adj[i].clear();
}
for (int i=1; i<=n; i++){
if (i!=root(i) or is_deactivated[i]) continue;
for (int key:key_store[i]) key_is_available[key]=1;
for (pair <int,int> p:edge_store[i]){
int key= p.first, room= p.second;
room= root(room);
if (i==room) continue;
if (key_is_available[key]) {
extended_adj[i].push_back(room);
if (is_deactivated[room]==0) adj[i].push_back(room);
rev_adj[room].push_back(i);
}
}
for (int key:key_store[i]) key_is_available[key]=0;
}
}
vector <int> terminals;
int vis[maxn];
void rev_dfs (int v){
vis[v]=1;
is_deactivated[v]=1;
for (int u:rev_adj[v]) if (!vis[u]) rev_dfs(u);
}
void deactivate_bad_nodes (int n){
terminals.clear();
for (int i=1; i<=n; i++) vis[i]=0;
for (int i=1; i<=n; i++) {
if (i==root(i)){
if (is_deactivated[i]==1) rev_dfs(i);
else{
if (extended_adj[i].size()==0){
is_deactivated[i]=1;
for (int room:room_store[i]) ans[room]= sz[i];
rev_dfs(i);
}
}
}
}
}
int scc_par[maxn], scc_visited[maxn];
vector <int> ordering;
int bad_count=0;
void scc_dfs (int v){
scc_visited[v]=1;
bad_count++;
//cout<<"bad count "<<bad_count<<endl;
// cout<<v<<" "<<"NEXT "<<endl;
//for (int u:adj[v]) cout<<u<<" ";
// cout<<endl;
for (int u:adj[v]){
if (!scc_visited[u]) {
scc_dfs(u);
}
}
ordering.push_back(v);
}
void scc_rev_dfs (int v, int p){
scc_par[v]=p;
for (int u:rev_adj[v]){
if (scc_par[u]==0) scc_rev_dfs(u, p);
}
}
vector <int> compressed_dag_edges[maxn];
int terminal_children[maxn][2];
int done_collecting_information[maxn];
void collect_information (int v){
done_collecting_information[v]=1;
if (compressed_dag_edges[v].empty()){
terminal_children[v][0]= v;
terminal_children[v][1]= -1;
}
else{
vector <int> reachable_terminals;
for (int w:compressed_dag_edges[v]){
if (!done_collecting_information[w]) collect_information(w);
if (terminal_children[w][0]!=-1 and reachable_terminals.size()<2) reachable_terminals.push_back(terminal_children[w][0]);
if (terminal_children[w][1]!=-1 and reachable_terminals.size()<2) reachable_terminals.push_back(terminal_children[w][1]);
}
if (reachable_terminals.size()>=2){
terminal_children[v][0]= reachable_terminals[0];
terminal_children[v][1]= reachable_terminals[1];
}
if (reachable_terminals.size()==1){
terminal_children[v][0]= reachable_terminals[0];
terminal_children[v][1]= -1;
}
}
}
int check_if_valid (int v, int terminal_id){
v= scc_par[v];
if (terminal_children[v][0]==terminal_id and terminal_children[v][1]==-1) return 1;
if (terminal_children[v][1]==terminal_id and terminal_children[v][0]==-1) return 1;
return 0;
}
vector <int> expanded_sccs[maxn];
vector <int> store_scc[maxn];
void find_sccs (int n){
ordering.clear();
for (int i=1; i<=n; i++){
scc_par[i]=0;
scc_visited[i]=0;
done_collecting_information[i]=0;
store_scc[i].clear();
compressed_dag_edges[i].clear();
terminal_children[i][0]= -1;
terminal_children[i][1]=-1;
}
for (int i=1; i<=n; i++){
if (i==root(i) and !is_deactivated[i] and !scc_visited[i]) {
// cout<<"visiting "<<i<<endl;
scc_dfs(i);
}
}
reverse(ordering.begin(), ordering.end());
for (int u:ordering) if (scc_par[u]==0) scc_rev_dfs(u, u);
for (int i=1; i<=n; i++){
if (scc_par[i]!=0 and i==root(i) and !is_deactivated[i]) store_scc[scc_par[i]].push_back(i);
}
for (int i=1; i<=n; i++){
if (i==root(i) and !is_deactivated[i]){
for (int v:adj[i]){
if (scc_par[v]!=scc_par[i]) {
int comp_i= scc_par[i], comp_v= scc_par[v];
compressed_dag_edges[comp_i].push_back(comp_v);
}
}
}
}
for (int i=1; i<=n; i++){
if (i==root(i) and !is_deactivated[i] and i==scc_par[i] and !done_collecting_information[i]) collect_information(i);
}
}
int expansion_is_key_available[maxn], expansion_is_vertex_visited[maxn];
vector <int > edges_by_key[maxn];
vector <int> list_of_vertices, list_of_keys;
void expansion_process_vertex (int v, int terminal_id){
for (int key:key_store[v]) {
if (!expansion_is_key_available[key]) {
list_of_keys.push_back(key);
expansion_is_key_available[key]=1;
for (int other_vertex:edges_by_key[key]){
if (!expansion_is_vertex_visited[other_vertex]) {
list_of_vertices.push_back(other_vertex);
expansion_is_vertex_visited[other_vertex]=1;
}
}
edges_by_key[key].clear();
}
}
for (pair<int,int> p:edge_store[v]){
int key= p.first, room= p.second;
room= root(room);
if (key_is_available[key]){
if (!expansion_is_vertex_visited[room] and check_if_valid(room, terminal_id)){
expansion_is_vertex_visited[room]=1;
list_of_vertices.push_back(room);
}
}
else{
if (!expansion_is_vertex_visited[room] and check_if_valid(room, terminal_id)) edges_by_key[key].push_back(room);
}
}
}
void expand_terminal (int terminal_id){
if (terminal_id!=root(terminal_id) or terminal_id!=scc_par[terminal_id] or is_deactivated[terminal_id]) return;
expanded_sccs[terminal_id].push_back(terminal_id);
if (compressed_dag_edges[terminal_id].size()>0) return;
for (int vertex:store_scc[terminal_id]){
list_of_vertices.push_back(vertex);
expansion_is_vertex_visited[vertex]=1;
for (int key:key_store[vertex]) {
list_of_keys.push_back(key);
expansion_is_key_available[key]=1;
}
}
for (int i=0; i<(int) list_of_vertices.size(); i++){
int cur_vertex= list_of_vertices[i];
expansion_process_vertex(cur_vertex, terminal_id);
}
for (int vertex:list_of_vertices) expanded_sccs[terminal_id].push_back(scc_par[vertex]);
for (int key:list_of_keys) expansion_is_key_available[key]=0;
for (int vertex:list_of_vertices) expansion_is_vertex_visited[vertex]=0;
list_of_vertices.clear();
list_of_keys.clear();
}
void process_sccs (int n){
for (int i=1; i<=n; i++) expanded_sccs[i].clear();
for (int i=1; i<=n; i++) expand_terminal(i);
for (int i=1; i<=n; i++){
if (expanded_sccs[i].size()>0){
int representative_scc=expanded_sccs[i][0];
int representative_vertex= store_scc[representative_scc][0];
for (int scc:expanded_sccs[i]){
for (int vertex:store_scc[scc]) merge(representative_vertex, vertex);
}
}
}
}
void process_one_round(int n){
add_edges(n);
// cout<<"edges added"<<endl;
find_sccs(n);
// cout<<"sccs found "<<endl;
process_sccs(n);
// cout<<"Sccs expanded "<<endl;
add_edges(n);
// cout<<"new edges added "<<endl;
deactivate_bad_nodes(n);
// cout<<"bad nodes deactivated "<<endl;
}
void init(int n){
for (int i=1; i<=n; i++){
par[i]=i;
sz[i]=1;
ans[i]= -1;
key_store[i].clear();
room_store[i].clear();
room_store[i].push_back(i);
edge_store[i].clear();
expanded_sccs[i].clear();
store_scc[i].clear();
compressed_dag_edges[i].clear();
is_deactivated[i]=0;
}
}
vector <int> get_answer(int n){
print_flag=1;
for (int i=1; i<=20; i++) {
process_one_round(n);
if (i>1) print_flag=0;
}
int mn_ans = n;
for (int i=1; i<=n; i++){
if (ans[i]!=-1) mn_ans= min(mn_ans, ans[i]);
}
vector <int> output;
for (int i=1; i<=n; i++) {
if (mn_ans==ans[i]) output.push_back(1);
else output.push_back(0);
}
return output;
}
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();
init(n);
for (int i=1; i<=n; i++){
key_store[i].push_back(r[i-1]+1);
}
for (int ed=0; ed<(int) u.size(); ed++){
int endpoint_1= u[ed]+1, endpoint_2= v[ed]+1, key= c[ed]+1;
edge_store[endpoint_1].push_back(make_pair(key, endpoint_2));
edge_store[endpoint_2].push_back(make_pair(key, endpoint_1));
}
return get_answer(n);
}
int main() {
return 0;
}
