#include <bits/stdc++.h>
#ifndef LOCAL
#include "werewolf.h"
#endif
using namespace std;
const int N = 200'000 + 10;
int n, m, q;
vector<int> ad[N];
struct Edge {
int u, v;
} edge[N << 1];
struct couldCan {
vector<int> ad[N << 1];
int f[N << 1][19];
int sz[N << 1], st[N << 1], ed[N << 1], it;
int w[N << 1];
int id[N << 1];
couldCan() { memset(id, -1, sizeof id); }
int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
void add(int u, int v) {
u = root(u); v = root(v);
if (u == v) return;
if (u < v) swap(u, v);
id[v] = u;
}
void dfs(int u, int p = -1) {
for (int i = 1; i <= 18; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
st[u] = ++it;
for (const auto& v : ad[u]) {
f[v][0] = u;
dfs(v, u);
sz[u] += sz[v] + 1;
}
ed[u] = it;
}
} T[2];
struct Query {
int v, idx;
};
vector<Query> Q[N << 1];
struct BIT {
int n;
int bit[N << 1], g[N << 1], idx;
void clear() { idx += 1; }
int& val(int i) {
if (g[i] != idx) {
bit[i] = 0;
g[i] = idx;
}
return bit[i];
}
void upd(int i, int x) {
for (; i <= n; i += i & -i) val(i) += x;
}
int que(int i) {
int ret = 0;
for (; i; i -= i & -i) ret += val(i);
return ret;
}
} f;
bool answer[N];
vector<int> node;
void get(int u) {
if (u < n) node.push_back(u);
for (const auto& v : T[0].ad[u]) get(v);
}
void dfs(int u) {
sort(T[0].ad[u].begin(), T[0].ad[u].end(), [&](const auto& a, const auto& b) {
return T[0].sz[a] < T[0].sz[b];
});
int heavy = (!T[0].ad[u].size() ? -1 : T[0].ad[u].end()[-1]);
f.clear();
for (const auto& v : T[0].ad[u]) {
dfs(v);
}
node.clear();
for (const auto& v : T[0].ad[u]) if (v != heavy) get(v);
if (u < n) f.upd(T[1].st[u], 1);
for (const auto& x : node) f.upd(T[1].st[x], 1);
for (const auto& [v, idx] : Q[u]) {
answer[idx] = f.que(T[1].ed[v]) - f.que(T[1].st[v] - 1);
}
}
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_; m = x.size(); q = s.size();
for (int i = 0; i < m; ++i) {
int u = x[i], v = y[i];
ad[u].push_back(v);
ad[v].push_back(u);
edge[i] = {u, v};
}
for (int t = 0; t < 2; ++t) {
auto& tree = T[t];
auto weight = [&](const auto& edge) {
if (!t) return min(edge.u, edge.v);
return max(edge.u, edge.v);
};
sort(edge, edge + m, [&](const auto& a, const auto& b) {
if (!t) return weight(a) > weight(b);
return weight(a) < weight(b);
});
int it = n - 1;
for (int i = 0; i < m; ++i) {
auto [u, v] = edge[i];
int w = weight(edge[i]);
if (tree.root(u) == tree.root(v)) continue;
it += 1;
tree.add(it, u = tree.root(u)); tree.add(it, v = tree.root(v));
tree.ad[it].push_back(u);
tree.ad[it].push_back(v);
tree.w[it] = w;
}
tree.dfs(tree.f[it][0] = it);
}
for (int i = 0; i < q; ++i) {
{ //human
const auto& tree = T[0];
for (int j = 18; j >= 0; --j) if (tree.w[tree.f[s[i]][j]] >= l[i]) s[i] = tree.f[s[i]][j];
}
{ //wolf
const auto& tree = T[1];
for (int j = 18; j >= 0; --j) if (tree.w[tree.f[e[i]][j]] <= r[i]) e[i] = tree.f[e[i]][j];
}
Q[s[i]].push_back({e[i], i});
}
f.n = T[1].it;
dfs(T[0].it - 1);
return vector<int>(answer, answer + q);
}
#ifdef LOCAL
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n_, m_, q_; cin >> n_ >> m_ >> q_;
vector<int> x_(m_), y_(m_), s_(q_), e_(q_), l_(q_), r_(q_);
for (int j = 0; j < m_; ++j) cin >> x_[j] >> y_[j];
for (int i = 0; i < q_; ++i) cin >> s_[i] >> e_[i] >> l_[i] >> r_[i];
for (const auto& x : check_validity(n_, x_, y_, s_, e_, l_, r_)) cerr << x << "\n";
}
#endif
