#include "werewolf.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, q;
vector<ll> fadj[200005], adj[2][200005];
ll par[2][200005];
ll find(ll x, bool b) {
return (par[b][x] == x ? x : par[b][x] = find(par[b][x], b));
}
void merge(ll x, ll y, bool b) {
y = find(y, b);
adj[b][x].push_back(y);
par[b][y] = x;
}
ll twok[2][20][200005], pre[2][200005], unpre[2][200005], cnt[2], pos[2][200005];
void dfs(ll nd, ll pr, bool b) {
unpre[b][cnt[b]] = nd;
pre[b][nd] = cnt[b]++;
twok[b][0][nd] = pr;
iloop(1, 20) {
if (twok[b][i-1][nd] == -1) continue;
twok[b][i][nd] = twok[b][i-1][twok[b][i-1][nd]];
}
for (auto it : adj[b][nd]) dfs(it, nd, b);
pos[b][nd] = cnt[b] - 1;
}
struct node {
ll s, e, m, v;
node *l, *r;
node (ll S, ll E) {
s = S, e = E, m = (S+E)>>1, v = 0;
if (s != e) {
l = new node(s, m);
r = new node(m+1, e);
}
}
node (ll S, ll E, ll V) {
s = S, e = E, m = (S+E)>>1, v = V;
}
node (ll S, ll E, node *L, node *R) {
s = S, e = E, m = (S+E)>>1;
l = L, r = R;
v = l->v + r->v;
}
};
node* upd(ll X, ll V, node* nd) {
if (nd->s == nd->e) return new node(nd->s, nd->e, nd->v + V);
if (X <= nd->m) return new node(nd->s, nd->e, upd(X, V, nd->l), nd->r);
return new node(nd->s, nd->e, nd->l, upd(X, V, nd->r));
}
ll qu(ll S, ll E, node* nd) {
if (nd->s == S && nd->e == E) return nd->v;
if (E <= nd->m) return qu(S, E, nd->l);
if (S > nd->m) return qu(S, E, nd->r);
return qu(S, nd->m, nd->l) + qu(nd->m + 1, E, nd->r);
}
vector<node*> roots;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
memset(twok, -1, sizeof(twok));
n = N, q = S.size();
jloop(0, 2) iloop(0, n) par[j][i] = i;
iloop(0, (ll)X.size()) {
fadj[X[i]].push_back(Y[i]);
fadj[Y[i]].push_back(X[i]);
}
iloop(0, n) for (auto it : fadj[i]) if (it < i && find(i, 0) != find(it, 0)) merge(i, it, 0);
iloop(n-1, -1) for (auto it : fadj[i]) if (it > i && find(i, 1) != find(it, 1)) merge(i, it, 1);
dfs(n-1, -1, 0);
dfs(0, -1, 1);
roots.push_back(new node(0, n-1));
iloop(0, n) roots.push_back(upd(pre[1][unpre[0][i]], 1, roots.back()));
vector<int> ans;
iloop(0, q) {
if (S[i] < L[i] || E[i] > R[i]) {ans.push_back(0); continue;}
jloop(19, -1) if (twok[1][j][S[i]] != -1 && twok[1][j][S[i]] >= L[i]) S[i] = twok[1][j][S[i]];
jloop(19, -1) if (twok[0][j][E[i]] != -1 && twok[0][j][E[i]] <= R[i]) E[i] = twok[0][j][E[i]];
ans.push_back(qu(pre[1][S[i]], pos[1][S[i]], roots[pos[0][E[i]] + 1]) > qu(pre[1][S[i]], pos[1][S[i]], roots[pre[0][E[i]]]));
}
return ans;
}
