#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif
const int LG = 18;
struct DSU {
vector<int> parent,SIZE;
DSU(int n) {
parent.resize(n);
SIZE.resize(n);
for(int i=0;i<n;i++) {
parent[i] = i;
SIZE[i] = 1;
}
}
int find_set(int u) {
if(u == parent[u]) return u;
return parent[u] = find_set(parent[u]);
}
void union_sets(int u,int v) {
u = find_set(u);
v = find_set(v);
SIZE[u] += SIZE[v];
parent[v] = u;
}
};
vector<int> tree1(int n,vector<vector<int>> &g,vi &in,vi &out,vi &par) {
in.resize(n); out.resize(n);
DSU d(n); vector<vector<int>> g1(n);
for(int i=n-1;i>=0;i--) {
for(int u : g[i]) {
if(u < i or d.find_set(u) == i) continue;
u = d.find_set(u);
d.union_sets(i,u);
g1[i].pb(u);
par[u] = i;
}
}
vector<int> tour; int timer = -1;
function<void(int)> dfs = [&](int u) {
in[u] = ++timer;
tour.pb(u);
for(int i : g1[u]) {
dfs(i);
} out[u] = timer;
}; dfs(0);
return tour;
}
vector<int> tree2(int n,vector<vector<int>> &g,vi &in,vi &out,vi &par) {
in.resize(n); out.resize(n);
DSU d(n); vector<vector<int>> g2(n);
for(int i=0;i<n;i++) {
for(int u : g[i]) {
if(u > i or d.find_set(u) == i) continue;
u = d.find_set(u);
d.union_sets(i,u);
g2[i].pb(u);
par[u] = i;
}
}
vector<int> tour; int timer = -1;
function<void(int)> dfs = [&](int u) {
in[u] = ++timer;
tour.pb(u);
for(int i : g2[u]) {
dfs(i);
} out[u] = timer;
}; dfs(n-1);
return tour;
}
void transform1(int &S,int L,vector<vector<int>> &jmp) {
for(int i=LG-1;i>=0;i--) {
if(jmp[S][i] >= L) {
S = jmp[S][i];
}
}
}
void transform2(int &E,int R,vector<vector<int>> &jmp) {
for(int i=LG-1;i>=0;i--) {
if(jmp[E][i] <= R) {
E = jmp[E][i];
}
}
}
template<typename Node>
struct Segtr {
int s;
vector<Node> tree;
void build(int v,int tl,int tr,vector<int> &arr) {
if(tl == tr) {
tree[v] = Node(arr[tl]);
}else {
int tm = (tl + tr)/2;
build(2*v,tl,tm,arr); build(2*v+1,tm+1,tr,arr);
tree[v].merge(tree[2*v],tree[2*v+1]);
}
}
bool ok(Node &v,int L,int R) {
if(L > R) return 0;
int n = v.srt.size();
int l = 0,r = n - 1;
while(l <= r) {
int m = (l + r)/2;
if(v.srt[m] > R) {
r = m - 1;
} else if(v.srt[m] < L) {
l = m + 1;
} else return 1;
}
return 0;
}
bool check(int v,int l,int r,int tl,int tr,int L,int R) {
if(l > r) return 0;
else if(tl == l && tr == r) return ok(tree[v],L,R);
int tm = (tl + tr)/2;
bool lo = check(2*v,l,min(r,tm),tl,tm,L,R),hi = check(2*v+1,max(l,tm+1),r,tm+1,tr,L,R);
return lo|hi;
}
Segtr(int n,vector<int> &arr) {
s = n;
tree.resize(4*n);
build(1,0,n-1,arr);
}
};
struct Node1 {
vector<int> srt;
void merge(Node1 &a,Node1 &b) {
std::merge(all(a.srt),all(b.srt),back_inserter(srt));
}
Node1() {srt = {};}
Node1(int a) {
srt.clear();
srt.pb(a);
}
};
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<vector<int>> g(N),jmp1,jmp2; int M = X.size(),Q = S.size();
vector<int> answer(Q,0); // *
for(int i=0;i<M;i++) g[X[i]].pb(Y[i]),g[Y[i]].pb(X[i]);
vector<int> in[2],out[2],par1(N,0),par2(N,N-1);
vi tour1 = tree1(N,g,in[0],out[0],par1),tour2 = tree2(N,g,in[1],out[1],par2);
jmp1 = vector<vi>(N,vi(LG,0));
jmp2 = vector<vi>(N,vi(LG,N-1));
for(int i=0;i<N;i++) {
jmp1[i][0] = par1[i];
for(int j=1;j<LG;j++) jmp1[i][j] = jmp1[jmp1[i][j-1]][j-1];
}
for(int i=N-1;i>=0;i--) {
jmp2[i][0] = par2[i];
for(int j=1;j<LG;j++) jmp2[i][j] = jmp2[jmp2[i][j-1]][j-1];
}
map<int,int> mp;
for(int i = 0;i < N;i++) mp[tour1[i]] = i;
for(int i = 0;i < N;i++) tour2[i] = mp[tour2[i]];
Segtr<Node1> T(N,tour2);
for(int i=0;i<Q;i++) {
if(L[i] > S[i] or R[i] < E[i]) answer[i] = 0;
else {
transform1(S[i],L[i],jmp1); transform2(E[i],R[i],jmp2);
answer[i] = T.check(1,in[1][E[i]],out[1][E[i]],0,N-1,in[0][S[i]],out[0][S[i]]);
}
} return answer;
}
