#include "werewolf.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
struct segtree{
int n;
vector<int>stmaxi, stmini;
segtree(int n):n(n), stmaxi(2*n), stmini(2*n){}
void update(int posi, int val){
posi+=n;
for(stmaxi[posi]=val, stmini[posi]=val ; posi>1 ; posi/=2){
stmaxi[posi/2]=max(stmaxi[posi], stmaxi[posi^1]);
stmini[posi/2]=min(stmini[posi], stmini[posi^1]);
}
}
int qmax(int l, int r){
r++;
int res=0;
for(l+=n, r+=n ; l<r ; l/=2, r/=2){
if(l&1) res=max(res, stmaxi[l++]);
if(r&1) res=max(res, stmaxi[--r]);
}
return res;
}
int qmin(int l, int r){
r++;
int res=1e9;
for(l+=n, r+=n ; l<r ; l/=2, r/=2){
if(l&1) res=min(res, stmini[l++]);
if(r&1) res=min(res, stmini[--r]);
}
return res;
}
};
vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
if(N>3000){
vector<vector<int>>g(N);
for(int i=0 ; i<(int)X.size() ; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int start;
for(int i=0 ; i<N ; i++){
if((int)g[i].size()==1){
start=i;
break;
}
}
// dbg(start)
queue<int>bfs;
bfs.push(start);
vector<int>vn, position(N);
segtree st(N+5);
vn.push_back(-1);
vn.push_back(start);
st.update(1, start);
position[start]=1;
vector<bool>vis(N);
vis[start]=1;
while(!bfs.empty()){
int u=bfs.front();
bfs.pop();
for(int v:g[u]){
if(!vis[v]){
vis[v]=1;
bfs.push(v);
vn.push_back(v);
// dbg(v)
// dbg((int)vn.size()-1);
st.update((int)vn.size()-1, v);
position[v]=(int)vn.size()-1;
}
}
}
// for(int i=0 ; i<N ; i++) dbg(position[i])
vector<int>ans((int)L.size());
for(int i=0 ; i<(int)L.size() ; i++){
// dbg(position[S[i]])
// dbg(position[E[i]])
if(position[S[i]]<=position[E[i]]){
int valenotta=position[S[i]], matijim=position[E[i]];
int l=position[S[i]], r=position[E[i]];
while(l<=r){
int mid=(l+r)/2;
// dbg(mid)
// dbg(position[S[i]])
// dbg(st.qmin(position[S[i]], mid))
if(st.qmin(position[S[i]], mid)<L[i]) r=mid-1;
else{
valenotta=mid;
l=mid+1;
}
}
l=position[S[i]], r=position[E[i]];
while(l<=r){
int mid=(l+r)/2;
if(st.qmax(mid, position[E[i]])>R[i]) l=mid+1;
else{
matijim=mid;
r=mid-1;
}
}
// dbg(valenotta)
// dbg(matijim)
if(matijim<=valenotta) ans[i]=1;
else ans[i]=0;
}else{
int valenotta=position[S[i]], matijim=position[E[i]];
int r=position[S[i]], l=position[E[i]];
while(l<=r){
int mid=(l+r)/2;
if(st.qmin(mid, position[S[i]])<L[i]) l=mid+1;
else{
valenotta=mid;
r=mid-1;
}
}
r=position[S[i]], l=position[E[i]];
while(l<=r){
int mid=(l+r)/2;
if(st.qmax(position[E[i]], mid)>R[i]) r=mid-1;
else{
matijim=mid;
l=mid+1;
}
}
if(matijim>=valenotta) ans[i]=1;
else ans[i]=0;
}
}
return ans;
}else{
vector<vector<int>>g(N);
for(int i=0 ; i<(int)X.size() ; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<int>ans((int)L.size());
for(int i=0 ; i<(int)L.size() ; i++){
queue<int>bfs;
vector<bool>vis(N);
bfs.push(S[i]);
vis[S[i]]=1;
while(!bfs.empty()){
int u=bfs.front();
bfs.pop();
for(int v:g[u]){
if(v>=L[i] && !vis[v]){
vis[v]=1;
bfs.push(v);
}
}
}
// for(bool x:vis) dbg(x)
bfs.push(E[i]);
vector<bool>vis1(N);
vis1[E[i]]=1;
bool ok=0;
if(vis[E[i]]) ok=1;
while(!bfs.empty()){
int u=bfs.front();
bfs.pop();
for(int v:g[u]){
if(v<=R[i]){
if(v>=L[i] && vis[v]==1) ok=1;
if(vis1[v]==1) continue;
vis1[v]=1;
bfs.push(v);
}
if(ok) break;
}
if(ok) break;
}
ans[i]=(ok?1:0);
}
return ans;
}
}
