/**
* Author : Nguyen Tuan Vu
* Created : 25.01.2023
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
const int MAXN = 4e5 + 5;
int n, m, nquery;
pair <int, int> edges[MAXN];
vector <int> adj[MAXN];
struct QUERY {
int s, t, l, r;
// constraints :
// For each query i : 0 <= i < Q
// 0 <= l(i) <= s(i) <= n - 1
// 0 <= e(i) <= r(i) <= n - 1
// s(i) != e(i)
// l(i) <= r(i)
QUERY() {}
QUERY(int s, int t, int l, int r) {
this->s = s;
this->t = t;
this->l = l;
this->r = r;
}
} q[MAXN];
namespace sub2 {
int dd[2][MAXN], cur;
void dfs(int type, int u, int i) {
if (dd[type][u] == cur) return;
//cout << u << ' ' << trans << '\n';
dd[type][u] = cur;
for (auto v : adj[u]) {
if (type == 0 && v >= q[i].l) {
dfs(type, v, i);
}
if (type == 1 && v <= q[i].r) {
dfs(type, v, i);
}
}
}
vector <int> solve() {
vector <int> tmp;
FOR(i, 1, nquery) {
++cur;
dfs(0, q[i].s, i);
dfs(1, q[i].t, i);
bool ok = 0;
REP(j, n) if (dd[0][j] == cur && dd[1][j] == cur) {
ok = 1;
break;
}
if (ok) tmp.push_back(1);
else tmp.push_back(0);
}
return tmp;
}
};
vector <int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> T, vector <int> L, vector <int> R) {
n = N; m = X.size(); nquery = S.size();
REP(i, m) {
edges[i + 1] = make_pair(X[i], Y[i]);
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
REP(i, nquery) q[i + 1] = QUERY(S[i], T[i], L[i], R[i]);
if (n <= 3000 && m <= 6000 && nquery <= 3000) return sub2::solve();
return vector <int> (nquery, 0);
}
