#include "werewolf.h"
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 1e6+5 , inf = 2e9 + 7 , block = 1000;
const ll INF = 1e18 , mod = 1e9+7;
int p[N][2] , sz[N][2];
int get(int a , int k){
if(p[a][k] == a) return a;
return p[a][k] = get(p[a][k],k);
}
void merge(int a , int b , int k){
a = get(a,k);
b = get(b,k);
if(a == b) return;
if(sz[a][k] < sz[b][k]) swap(a,b);
sz[a][k] += sz[b][k];
p[b][k] = a;
}
vector<int> g[N] , ord;
int spmn[N][20] , spmx[N][20] , lg[N] , pos[N];
void dfs(int v, int p){
ord.push_back(v);
for(int to : g[v]){
if(to != p) dfs(to,v);
}
}
void go(int n){
for(int i = 0; i < n; i++){
if(g[i].size() == 1){
dfs(i,0);
break;
}
}
for(int i = 0; i < ord.size(); i++){
pos[ord[i]] = i;
}
for(int i = 1; i <= n; i++){
lg[i] = lg[i/2]+1;
if(i == 1) lg[i] = 0;
}
for(int i = 0; i < n; i++){
spmn[i][0] = spmx[i][0] = ord[i];
}
for(int j = 1; j <= lg[n]; j++){
for(int i = 0; i + (1 << j) -1 < n; i++){
spmn[i][j] = min(spmn[i][j-1] , spmn[i+(1 << (j-1))][j-1]);
spmx[i][j] = max(spmx[i][j-1] , spmx[i+(1 << (j-1))][j-1]);
}
}
}
int getmx(int l , int r){
int len = lg[r-l+1];
return max(spmx[l][len] , spmx[r-(1 << len)+1][len]);
}
int getmn(int l , int r){
int len = lg[r-l+1];
return min(spmn[l][len] , spmn[r-(1 << len)+1][len]);
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e , vector<int> l, vector<int> r) {
vector<int> ans;
for(int i = 0; i < x.size(); i++){
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
int cnt = 0 , cnt2 = 0;
for(int i = 0; i < n; i++){
if(g[i].size() == 1) cnt++;
else if(g[i].size() == 2) cnt2++;
}
if(cnt == 2 && cnt2 == n-2){
go(n);
for(int i = 0; i < s.size(); i++){
if(pos[s[i]] < pos[e[i]]){
int L = pos[s[i]] , R = pos[e[i]] , res = pos[s[i]];
while(L <= R){
int md = (L+R) >> 1;
if(getmn(L,md) >= l[i]){
res = md;
L = md+1;
} else {
R = md-1;
}
}
int res1 = pos[e[i]];
L = pos[s[i]] , R = pos[e[i]];
while(L <= R){
int md = (L+R) >> 1;
if(getmx(md,R) <= r[i]){
res1 = md;
R = md-1;
} else {
L = md+1;
}
}
if(res >= res1){
ans.push_back(1);
} else {
ans.push_back(0);
}
} else {
int L = pos[e[i]] , R = pos[s[i]] , res = pos[e[i]];
while(L <= R){
int md = (L+R) >> 1;
if(getmx(L,md) <= r[i]){
res = md;
L = md+1;
} else {
R = md-1;
}
}
int res1 = pos[s[i]];
L = pos[e[i]] , R = pos[s[i]];
while(L <= R){
int md = (L+R) >> 1;
if(getmn(md,R) >= l[i]){
res1 = md;
R = md-1;
} else {
L = md+1;
}
}
if(res >= res1){
ans.push_back(1);
} else {
ans.push_back(0);
}
}
}
} else {
for(int i = 0; i < s.size(); i++){
for(int j = 0; j < n; j++){
p[j][0] = p[j][1] = j;
sz[j][0] = sz[j][1] = 1;
}
for(int j = 0; j < x.size(); j++){
if(x[j] >= l[i] && y[j] >= l[i]){
merge(x[j],y[j],0);
}
if(x[j] <= r[i] && y[j] <= r[i]){
merge(x[j],y[j],1);
}
}
int ok = 0;
for(int j = 0; j < n; j++){
if(get(s[i] , 0) == get(j , 0) && get(e[i] , 1) == get(j , 1)){
ok = 1;
break;
}
}
ans.push_back(ok);
}
}
return ans;
}
