#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 2e5 + 10;
int n , m , q , pos[N];
vector <int> adj[N] , vec;
struct SEG{
int mn[N << 2] , mx[N << 2];
void Build(int node = 1 , int nl = 0 , int nr = n)
{
if(nr - nl == 1)
{
mn[node] = mx[node] = vec[nl];
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid); Build(rc , mid , nr);
mn[node] = min(mn[lc] , mn[rc]);
mx[node] = max(mx[lc] , mx[rc]);
}
int Getmn(int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
if(nr <= l || r <= nl)
return n;
if(l <= nl && nr <= r)
return mn[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
return min(Getmn(l , r , lc , nl , mid) , Getmn(l , r , rc , mid , nr));
}
int Getmx(int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
if(nr <= l || r <= nl)
return 0;
if(l <= nl && nr <= r)
return mx[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
return max(Getmx(l , r , lc , nl , mid) , Getmx(l , r , rc , mid , nr));
}
} seg;
pair<int , int> Getst(int id , int val)
{
pair<int , int> res;
int low = -1 , high = id;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(seg.Getmn(mid , id + 1) >= val)
high = mid;
else
low = mid;
}
res.first = high;
low = id; high = n;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(seg.Getmn(id , mid + 1) >= val)
low = mid;
else
high = mid;
}
res.second = low;
return res;
}
pair<int , int> Getfn(int id , int val)
{
pair<int , int> res;
int low = -1 , high = id;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(seg.Getmx(mid , id + 1) <= val)
high = mid;
else
low = mid;
}
res.first = high;
low = id; high = n;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(seg.Getmx(id , mid + 1) <= val)
low = mid;
else
high = mid;
}
res.second = low;
return res;
}
vector <int> check_validity(int nn , vector <int> X , vector <int> Y , vector <int> S , vector <int> E , vector <int> L , vector <int> R )
{
vector <int> res;
n = nn;
m = X.size();
q = S.size();
for(int i = 0 ; i < m ; i++)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0 ; i < n ; i++) if(adj[i].size() == 1)
{
vec.push_back(i);
vec.push_back(adj[i][0]);
break;
}
while(vec.size() < n)
{
if(adj[vec.back()][0] == vec[vec.size() - 2])
vec.push_back(adj[vec.back()][1]);
else
vec.push_back(adj[vec.back()][0]);
}
for(int i = 0 ; i < n ; i++)
pos[vec[i]] = i;
seg.Build();
for(int i = 0 ; i < q ; i++)
{
pair<int ,int> a = Getst(pos[S[i]] , L[i]) , b = Getfn(pos[E[i]] , R[i]);
bool flg = true;
if(a.second < b.first || b.second < a.first)
flg = false;
res.push_back(flg);
}
return res;
}
