#include <bits/stdc++.h>
#define a first
#define b second
#define pb push_back
#define mk make_pair
#define node pair<int,int>
using namespace std;
const int NN = (2e5 + 5);
const int inf = (1e9 + 7);
int n,q,m;
int dev[NN];
int l = -1,r;
int fl = 0;
int a[NN],pos[NN],cn;
node t[NN * 4],cr;
int used[NN];
vector <int> ans,g[NN];
node combine(node a,node b) {
a.a = max(a.a,b.a);
a.b = min(a.b,b.b);
return a;
}
void build (int v = 1,int tl = 1,int tr = n) {
if (tl == tr) {
t[v].a = t[v].b = a[tl];
}
else {
int tm = (tl + tr) >> 1;
build (v + v,tl,tm);
build (v + v + 1,tm + 1,tr);
t[v] = combine(t[v + v],t[v + v + 1]);
}
}
node get (int l,int r,int v = 1,int tl = 1,int tr = n) {
if (tl > r || tr < l) return {0,inf};
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return combine(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
void man (int v,int mx) {
if (v < mx) return;
used[v] = 1;
for (auto to : g[v])
if (!used[to] && to >= mx) man(to,mx);
}
void wolf(int v,int mx) {
if (v > mx) return;
if (used[v] || fl) {
fl = 1;
return;
}
used[v] = 2;
for (auto to : g[v])
if (used[to] != 2 && to <= mx) wolf(to,mx);
}
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,q = S.size(),m = X.size();
for (int i = 0; i < m; i ++)
X[i] ++,Y[i] ++;
for (int i = 0; i < q; i ++)
S[i] ++,E[i] ++,L[i] ++,R[i] ++;
if (n <= 3000 && m <= 6000 && q <= 3000) {
for (int i = 0; i < m; i ++) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
for (int i = 0; i < q; i ++) {
int aa = S[i],bb = E[i],sl = L[i],sr = R[i];
for (int i = 1; i <= n; i ++)
used[i] = 0;
man(aa,sl);
wolf(bb,sr);
ans.pb(fl);
fl = 0;
}
return ans;
}
for (int i = 0; i < m; i ++) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
dev[X[i]] ++;
dev[Y[i]] ++;
}
for (int i = 1; i <= n; i ++) {
if (dev[i] == 1 && l == -1) l = i;
else if (dev[i] == 1) r = i;
}
int cur = l;
while (cur != r) {
a[++cn] = cur;
pos[cur] = cn;
if (a[cn - 1] != g[cur][0]) cur = g[cur][0];
else cur = g[cur][1];
}
a[++cn] = r;
pos[r] = cn;
build();
for (int i = 0; i < q; i ++) {
int aa = S[i],bb = E[i],sl = L[i],sr = R[i];
if (pos[aa] <= pos[bb]) {
int lo = pos[aa],hi = pos[bb];
while (hi - lo > 1) {
int md = (hi + lo) >> 1;
cr = get(pos[aa],md);
if (cr.b >= sl) lo = md;
else hi = md;
}
cr = get(pos[aa],hi);
if (cr.b >= sl) lo = hi;
l = pos[aa],r = pos[bb];
while (r - l > 1) {
int md = (r + l) >> 1;
cr = get(md,pos[bb]);
if (cr.a <= sr) r = md;
else l = md;
}
cr = get(l,pos[bb]);
if (cr.a <= sr) r = l;
if (r <= lo) ans.pb(1);
else ans.pb(0);
}
else {
int lo = pos[bb],hi = pos[aa];
while (hi - lo > 1) {
int md = (hi + lo) >> 1;
cr = get(pos[bb],md);
if (cr.a <= sr) lo = md;
else hi = md;
}
cr = get(pos[bb],hi);
if (cr.a <= sr) lo = hi;
l = pos[bb],r = pos[aa];
while (r - l > 1) {
int md = (r + l) >> 1;
cr = get(md,pos[aa]);
if (cr.b >= sl) r = md;
else l = md;
}
cr = get(l,pos[aa]);
if (cr.b >= sl) r = l;
if (r <= lo) ans.pb(1);
else ans.pb(0);
}
}
return ans;
}
