#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=300007;
const ll LG=25;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool used2[N];
ll tl[N][LG];
ll th[N][LG];
void dfs1(int v, int btm){
used[v]=true;
for(int to:g[v]){
if(!used[to]&&to>=btm){
dfs1(to,btm);
}
}
}
bool dfs2(int v, int top){
if(used[v])return true;
used2[v]=true;
for(int to:g[v]){
if(!used2[to]&&to<=top){
if(dfs2(to,top)){
return true;
}
}
}
return false;
}
void get_chain(int v, int par, vector<int>&ch){
ch.push_back(v);
for(int to:g[v]){
if(to!=par){
get_chain(to,v,ch);
}
}
}
void build_ST(vector<int>&a){
for(int i=0;i<a.size();i++){
tl[i][0]=a[i];
th[i][0]=a[i];
}
for(int j=1;j<LG;j++){
for(int i=0;i+(1<<(j-1))<a.size();i++){
tl[i][j]=min(tl[i][j-1],tl[i+(1<<(j-1))][j-1]);
th[i][j]=max(th[i][j-1],th[i+(1<<(j-1))][j-1]);
}
}
}
ll get_highest(int l, int r){
int len=r-l+1;
int lgf=(len ? __builtin_clzll(1) - __builtin_clzll(len) : -1);
return max(th[l][lgf],th[r-(1<<lgf)][lgf]);
}
ll get_lowest(int l, int r){
int len=r-l+1;
int lgf=(len ? __builtin_clzll(1) - __builtin_clzll(len) : -1);
return min(tl[l][lgf],tl[r-(1<<lgf)][lgf]);
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
n=NN;
m=X.size();
k=S.size();
for(int i=0;i<m;i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<int>ans;
if(n<=3000&&k<=3000&&m<=6000){
for(int i=0;i<k;i++){
dfs1(S[i],L[i]);
ans.push_back(dfs2(E[i],R[i]));
fill(used,used+n+1,false);
fill(used2,used2+n+1,false);
}
return ans;
}
int start=-1;
for(int v=0;v<n;v++){
if(g[v].size()==1){
start=v;
break;
}
}
vector<int>ch;
// cout<<"FIN1"<<endl;
get_chain(start, start, ch);
// cout<<"FIN2"<<endl;
build_ST(ch);
// cout<<"FIN3"<<endl;
vector<int>revch(ch.size(),0);
for(int i=0;i<ch.size();i++){
revch[ch[i]]=i;
}
// for(int x:revch)cout<<x<<" ";
// cout<<endl;
for(int i=0;i<k;i++){
int v=revch[S[i]];
int u=revch[E[i]];
// cout<<v<<" "<<u<<endl;
if(v<u){
int l=v,r=u+1;
while(l<r){
int mid=(l+r)/2;
if(get_lowest(v,mid)>=L[i]){
l=mid+1;
}
else{
r=mid;
}
}
int leftbound=l-1;
l=v,r=u+1;
while(l<r){
int mid=(l+r)/2;
if(get_highest(mid,u)<=R[i]){
r=mid;
}
else{
l=mid+1;
}
}
if(leftbound>=l-1){
ans.push_back(1);
}
else{
ans.push_back(0);
}
}
else{
swap(v,u);
int l=v,r=u+1;
while(l<r){
int mid=(l+r)/2;
if(get_highest(v,mid)<=R[i]){
l=mid+1;
}
else{
r=mid;
}
}
int leftbound=l-1;
l=v,r=u+1;
while(l<r){
int mid=(l+r)/2;
if(get_lowest(mid,u)>=L[i]){
r=mid;
}
else{
l=mid+1;
}
}
if(leftbound>=l-1){
ans.push_back(1);
}
else{
ans.push_back(0);
}
}
}
return ans;
}
