#include "werewolf.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define all(x) x.begin(),x.end()
using namespace std;
const int MAXN = 2e5+5 ;
bool visited0[MAXN];
int cnt , g_left[MAXN],g_right[MAXN],par[MAXN],pos[MAXN];
pi start_int[MAXN],end_int[MAXN];
vector<int> adj[MAXN] ;
void dfs0(int u){
visited0[u] = 1 ;
pos[u] = cnt ;
par[u] = u ;
cnt ++ ;
for(int v : adj[u]){
if( !visited0[v] ){
dfs0(v);
}
}
}
int fs(int u){
if( u == par[u] )return u ;
return par[u]=fs(par[u]) ;
}
void us(int u,int v){
u = fs(u) ;
v = fs(v) ;
if( u == v )return ;
par[v] = u ;
g_left[u] = min(g_left[u],g_left[v]);
g_right[u] = max(g_right[u],g_right[v]);
}
bool intersect(pi a,pi b){
return max(a.fi,b.fi)<=min(a.se,b.se);
}
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 M = sz(X);
vector<pair<int,int>> queries ;
int Q = sz(L);
vector<int> A(Q);
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++ ){
if( sz(adj[i])==1 ){
dfs0(i) ;
break ;
}
}
// cerr <<"****"<<endl;
// for(int i = 0 ; i < N ; i++ ){
// cout << i << " " << g_left[i] << " " << g_right[i]<<endl;
// }
// cerr <<"******"<<endl;
for(int i = 0 ; i < Q ; i++ ){
queries.pb({L[i],i});
}
sort(all(queries));
memset(g_left,-1,sizeof g_left);
memset(g_right,-1,sizeof g_right);
for(int i = N-1 , j = Q-1; i != -1 ; i-- ){
g_left[i] = pos[i] ;
g_right[i] = pos[i] ;
for(int v : adj[i]){
if(v>=i)
us(v,i);
}
while (j!=-1&&queries[j].fi == i ){
int x = queries[j].se ;
// cerr <<"ye " << S[x] << " " << fs(S[x])<< endl;
start_int[x] = {g_left[fs(S[x])],g_right[fs(S[x])]};
j--;
}
}
for(int i = 0 ; i < Q ; i++ ){
queries[i]={R[i],i} ;
}
sort(all(queries)) ;
memset(g_left,-1,sizeof g_left);
memset(g_right,-1,sizeof g_right);
for(int i = 0 ; i < N ; i++ )par[i] = i ;
for(int i = 0 , j = 0 ; i < N ; i++ ){
g_left[i] = pos[i] ;
g_right[i] = pos[i] ;
for(int v : adj[i]){
if( v <= i )
us(v,i);
}
while (j<Q&&queries[j].fi==i){
int x = queries[j].se ;
end_int[x] = {g_left[fs(E[x])],g_right[fs(E[x])]};
j++;
}
}
for(int i = 0 ; i < Q ; i++ ){
// cerr <<"query n "<<i<<"******";
// cerr << "start int "<< start_int[i].fi << " " << start_int[i].se <<endl;
// cerr << "end int "<< end_int[i].fi << " " << end_int[i].se <<endl;
A[i] = (start_int[i].fi != -1 && start_int[i].se != -1 && end_int[i].fi != -1 && end_int[i].se!=-1&&
intersect(start_int[i],end_int[i])) ;
}
return A;
}
// namespace {
// int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
// }
// } // namespace
// int main() {
// int N = read_int();
// int M = read_int();
// int Q = read_int();
// std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
// for (int j = 0; j < M; ++j) {
// X[j] = read_int()-1;
// Y[j] = read_int()-1;
// }
// for (int i = 0; i < Q; ++i) {
// S[i] = read_int()-1;
// E[i] = read_int()-1;
// L[i] = read_int()-1;
// R[i] = read_int()-1;
// }
// std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
// for (size_t i = 0; i < A.size(); ++i) {
// printf("%d\n", A[i]);
// }
// return 0;
// }
