#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "werewolf.h"
vector<int> par;
vector<vector<int> > adj1, adj2, adj;
int fnd(int a){
if(a == par[a]) return a;
return par[a] = fnd(par[a]);
}
bool merge(int a, int b, int g){
a = fnd(a), b = fnd(b);
if(a == b) return 0;
if(g == 0){
adj1[a].pb(b);
adj1[b].pb(a);
par[min(a, b)] = max(a, b);
}
else{
adj2[a].pb(b);
adj2[b].pb(a);
par[max(a, b)] = min(a, b);
}
return 1;
}
vector<int> in1, out1, in2, out2, p1, p2;
int timer;
void dfs1(int node, int par){
in1[node] = ++timer;
p1[node] = par;
for(auto itr: adj1[node]){
if(itr == par) continue;
dfs1(itr, node);
}
out1[node] = timer;
}
void dfs2(int node, int par){
in2[node] = ++timer;
p2[node] = par;
for(auto itr: adj2[node]){
if(itr == par) continue;
dfs2(itr, node);
}
out2[node] = timer;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
int q = S.size();
int m = X.size();
adj1.resize(N);
adj2.resize(N);
adj.resize(N);
par.resize(N);
in1.resize(N);
in2.resize(N);
out1.resize(N);
out2.resize(N);
p1.resize(N);
p2.resize(N);
for(int i = 0; i < m; i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
for(int i = 0; i < N; i++){
par[i] = i;
}
for(int i = 0; i < N; i++){
for(auto itr: adj[i]){
if(itr > i) continue;
merge(i, itr, 0);
}
} // adj1'i oluşturuyoruz -> werewolf path
for(int i = 0; i < N; i++){
par[i] = i;
}
for(int i = N-1; i >= 0; i--){
for(auto itr: adj[i]){
if(itr < i) continue;
merge(i, itr, 1);
}
} // adj2'yi oluşturuyoruz -> human path
timer = 0;
dfs1(N-1, N-1);
timer = 0;
dfs2(0, 0);
/*
for(int i = 0; i < N; i++){
cout<<i<<" -> "<<in1[i]<<" "<<out1[i]<<" ve 2. agac "<<in2[i]<<" "<<out2[i]<<endl;
}*/
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
int start = S[i], finish = E[i];
while(start != 0 && p2[start] >= L[i]) start = p2[start];
while(finish != N-1 && p1[finish] <= R[i]) finish = p1[finish];
//cout<<i<<" "<<start<<" "<<finish<<endl;
bool ortak = 0;
for(int j = L[i]; j <= R[i]; j++){
bool anc2 = (in2[start] <= in2[j] && out2[start] >= out2[j]);
bool anc1 = (in1[finish] <= in1[j] && out1[finish] >= out1[j]);
if(anc1 && anc2){
ortak = true;
//cout<<i<<" -> "<<j<<" ok "<<endl;
}
}
if(ortak) ans[i] = 1;
}
return ans;
}
