#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
int n, m, q;
vector<int> ans;
vector<int> link[200002];
vector<int> order;
int idx[200002];
int MIN[800002], MAX[800002];
void init(int i, int l, int r){
if(l==r){
MIN[i] = MAX[i] = order[l];
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
MIN[i] = min(MIN[i*2], MIN[i*2+1]);
MAX[i] = max(MAX[i*2], MAX[i*2+1]);
}
int rangeMin(int i, int l, int r, int s, int e){
if(s<=l && r<=e) return MIN[i];
if(r<s || e<l) return INT_MAX;
int m = (l+r)>>1;
return min(rangeMin(i*2, l, m, s, e), rangeMin(i*2+1, m+1, r, s, e));
}
int rangeMax(int i, int l, int r, int s, int e){
if(s<=l && r<=e) return MAX[i];
if(r<s || e<l) return INT_MIN;
int m = (l+r)>>1;
return max(rangeMax(i*2, l, m, s, e), rangeMax(i*2+1, m+1, r, s, e));
}
int bigLim(int i, int l, int r, int x, int lim, int dir){ /// dir 0: left, 1: right
if(MIN[i] >= lim) return (dir == 0 ? l-1 : r+1);
if(l==r) return l;
int m = (l+r)>>1;
if(dir == 0){
if(x <= m) return bigLim(i*2, l, m, x, lim, dir);
int tmp = bigLim(i*2+1, m+1, r, x, lim, dir);
if(tmp != m) return tmp;
return bigLim(i*2, l, m, x, lim, dir);
}
else{
if(x > m) return bigLim(i*2+1, m+1, r, x, lim, dir);
int tmp = bigLim(i*2, l, m, x, lim, dir);
if(tmp != m+1) return tmp;
return bigLim(i*2+1, m+1, r, x, lim, dir);
}
}
int smallLim(int i, int l, int r, int x, int lim, int dir){ /// dir 0: left, 1: right
if(MAX[i] <= lim) return (dir == 0 ? l-1 : r+1);
if(l==r) return l;
int m = (l+r)>>1;
if(dir == 0){
if(x <= m) return smallLim(i*2, l, m, x, lim, dir);
int tmp = smallLim(i*2+1, m+1, r, x, lim, dir);
if(tmp != m) return tmp;
return smallLim(i*2, l, m, x, lim, dir);
}
else{
if(x > m) return smallLim(i*2+1, m+1, r, x, lim, dir);
int tmp = smallLim(i*2, l, m, x, lim, dir);
if(tmp != m+1) return tmp;
return smallLim(i*2+1, m+1, r, x, lim, dir);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N, m = (int)X.size(), q = (int)L.size();
ans.resize(q);
for(int i=0; i<m; i++){
link[X[i]].push_back(Y[i]);
link[Y[i]].push_back(X[i]);
}
for(int i=0; i<n; i++){
if(link[i].size() == 1){
order.push_back(i);
break;
}
}
while((int)order.size() < n){
int tmp = order.back(), tmp2 = link[tmp][0];
order.push_back(tmp2);
link[tmp2].erase(find(link[tmp2].begin(), link[tmp2].end(), tmp));
}
for(int i=0; i<n; i++) idx[order[i]] = i;
init(1, 0, n-1);
for(int i=0; i<q; i++){
int s = idx[S[i]], e = idx[E[i]], l = L[i], r = R[i];
if(s < e){
ans[i] = bigLim(1, 0, n-1, s, l, 1) - 1 > smallLim(1, 0, n-1, e, r, 0);
}
else{
ans[i] = bigLim(1, 0, n-1, s, l, 0) + 1 < smallLim(1, 0, n-1, e, r, 1);
}
}
return ans;
}
