#ifndef LOCAL
#include <bits/stdc++.h>
#include "werewolf.h"
#endif
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("avx2")
#ifdef LOCAL
#include "algo/debug.h"
#else
template <typename... Args>
void dummy(Args&&... args){}
#define ps dummy
#endif
#define f first
#define s second
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define len(x) (int)((x).size())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define ai2 array<int,2>
#define ai3 array<int,3>
#define ai4 array<int,4>
#define ai5 array<int,5>
template<class T> int lwb(const V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(const V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define clz __builtin_clzll
constexpr int p2(int x) { return (int)1 << x; }
constexpr int msk2(int x) { return (int)(1 << x) - 1; }
constexpr int bits(int x) { return x == 0 ? 0 : 63-clz(x); } // floor(log2(x))
template<class T>void UNIQUE(V<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }
template<class T, class Cmp>void UNIQUE(V<T>& v, Cmp cmp) { sort(all(v), cmp); v.erase(unique(all(v)),end(v)); }
template<class T,class U>void erase(T& t, const U& u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }
template<class F> struct y_combinator_result {
F f;
template<class T> explicit y_combinator_result(T &&f): f(std::forward<T>(f)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return f(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) yy(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
template<class T> struct Bit {
int n;
V<T> a;
void point_add(int i, T x) {
for (; i <= n; i += i & -i) {
a[i] += x;
}
}
T prefix_sum(int r) {
T res = 0;
for (; r > 0; r -= r & -r) {
res += a[r];
}
return res;
}
T query(int l, int r) { return prefix_sum(r) - prefix_sum(l - 1); }
Bit(int n) : n(n), a(n + 1) {}
};
const int LOG = 20;
struct Dsu {
int timer;
vector<int> par, tin, tout, order;
vector<vector<int>> adj;
Dsu(int n) : timer(0), par(n), tin(n), tout(n), order({n}), adj(n) {
iota(par.begin(), par.end(), 0);
}
int find(int u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if (u == v)
return;
par.push_back((int) par.size());
par[u] = par[v] = (int) par.size() - 1;
tin.emplace_back();
tout.emplace_back();
adj.push_back({u, v});
}
void dfs(int u) {
tin[u] = ++timer;
order.push_back(u);
for (int v : adj[u])
dfs(v);
tout[u] = timer;
}
};
#ifdef LOCAL
void solve() {
int N, M, Q; cin >> N >> M >> Q;
vi X(M), Y(M);
for (int i = 0; i < M; i++) cin >> X[i] >> Y[i];
vi S(Q), E(Q), L(Q), R(Q);
for (int i = 0; i < Q; i++) cin >> S[i] >> E[i] >> L[i] >> R[i];
#else
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int Q = len(S);
int M = len(X);
#endif
V<vi> g(N);
for (int i = 0; i < M; i++) g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]);
V<vi> query_l(N), query_r(N);
for (int i = 0; i < Q; i++) {
query_l[L[i]].pb(i);
query_r[R[i]].pb(i);
}
Dsu inc(N), dec(N);
for (int u = 0; u < N; u++) {
for (int v : g[u]) if (v < u) inc.unite(u, v);
for (int qi : query_r[u]) E[qi] = inc.find(E[qi]);
}
for (int u = N - 1; u >= 0; u--) {
for (int v : g[u]) if (v > u) dec.unite(u, v);
for (int qi : query_l[u]) S[qi] = dec.find(S[qi]);
}
inc.dfs(inc.find(0));
dec.dfs(dec.find(0));
// for each query, we want to find the number of shared values b/w
// inc.order[inc.tin[E[qi]], inc.tout[E[qi]]] and dec.order[dec.tin[S[qi]], dec.tout[S[qi]]]
// where S[qi] and E[qi] represent the nodes in the KRT for all >= L and <= R, respectievly.
int o1 = inc.order.size(), o2 = dec.order.size();
V<V<ai2>> evs(o1);
Bit<int> bit(o2);
for (int qi = 0; qi < Q; qi++) {
evs[inc.tin[E[qi]] - 1].pb({ qi, -1 });
evs[inc.tout[E[qi]]].pb({ qi, 1 });
}
vi ans(Q);
for (int i = 0; i < o1; i++) {
if (inc.order[i] < N) {
bit.point_add(dec.tin[inc.order[i]], 1);
}
for (auto [qi, sign] : evs[i]) {
ans[qi] += sign * bit.query(dec.tin[S[qi]], dec.tout[S[qi]]);
}
}
// vector evs(o1, V<ai4>());
// for (int qi = 0; qi < Q; qi++) {
// int l_a = dec.tin[S[qi]], r_a = dec.tout[S[qi]];
// int l_b = inc.tin[E[qi]], r_b = dec.tout[E[qi]];
// ps(l_b, r_b, N);
// evs[r_b].pb({ l_a, r_a, 1, qi });
// evs[l_b].pb({ l_a, r_a, -1, qi });
// }
// vi ans(Q);
// Bit<int> bit(N);
// for (int i = 0; i <= N; i++) {
// for (auto [l_a, r_a, sign, qi] : evs[i]) {
// ans[qi] += sign * (bit.prefix_sum(r_a + 1) - bit.prefix_sum(l_a));
// }
// if (i < N) bit.point_add(inc.tin[inc.order[i]], 1);
// }
for (int& i : ans) i = bool(i);
#ifdef LOCAL
for (int i : ans) cout << i << '\n';
#else
return ans;
#endif
}
#ifdef LOCAL
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
#endif
