两种形态都对经过的路程有限制，我们可以联想到克鲁斯卡尔重构树。

我们考虑将点权转化为边权，因为我们走这条边的话两个端点都要符合条件，所以人形态是边权为边的两个端点的较小值，狼形态相反。

人形态时要建一个最大生成树，狼形态相反

然后我们就可以知道人形态时起点可以到达哪些点，狼形态时哪些点可以到达终点。

怎么判又没有交集呢？因为树上一个子树的 \(dfs\) 序是连续的，我们可以以第一棵树为基础建立主席树，查询的时候只用看相应的区间是否为空就行了。

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n, m, q, x, y, num, l, r, cnt, s, t;
const int N = 400010;
int fa[N], root[N], lson[N * 21], rson[N * 21], siz[N * 21];
struct bian {int x, y, z;} e[N];
int my1(bian a, bian b) {return a.z > b.z;}
int my2(bian a, bian b) {return a.z < b.z;}
int find(int x) {return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);}
struct Tu
{
	int tot, cnt;
	int head[N], to[N], nt[N], val[N], fa[N][21], siz[N], dfn[N], nfd[N]; //19
	void add(int f, int t)
	{
		to[++tot] = t; nt[tot] = head[f]; head[f] = tot;
	}
	void dfs(int x)
	{
		siz[x] = 1; dfn[x] = ++cnt; nfd[cnt] = x;
		for (int i = 1; i <= 19; ++i)
			fa[x][i] = fa[fa[x][i - 1]][i - 1];
		for (int i = head[x]; i; i = nt[i])
			if (to[i] != fa[x][0])dfs(to[i]), siz[x] += siz[to[i]];
	}
	int find(int x, int v, int opt)
	{
		for (int i = 19; i >= 0; --i)
		{
			if (opt == 1) {if (fa[x][i] && val[fa[x][i]] >= v)x = fa[x][i];}
			else {if (fa[x][i] && val[fa[x][i]] <= v)x = fa[x][i];}
		}
		return x;
	}
} X1, X2;
void klske()
{
	for (int i = 1; i <= m; ++i)e[i].z = min(e[i].x, e[i].y); //人
	for (int i = 1; i <= (n << 1); ++i)fa[i] = i; num = n;
	sort(e + 1, e + 1 + m, my1);
	for (int i = 1; i <= m; ++i)
	{
		x = find(e[i].x); y = find(e[i].y);
		if (x == y)continue;
		X1.val[++num] = e[i].z;
		X1.add(num, x); X1.add(num, y);
		X1.fa[x][0] = num; X1.fa[y][0] = num;
		fa[x] = num; fa[y] = num;
		if (num - n == n - 1)break;
	}
	X1.dfs(find(1));

	for (int i = 1; i <= m; ++i)e[i].z = max(e[i].x, e[i].y); //狼
	for (int i = 1; i <= (n << 1); ++i)fa[i] = i; num = n;
	sort(e + 1, e + 1 + m, my2);
	for (int i = 1; i <= m; ++i)
	{
		x = find(e[i].x); y = find(e[i].y);
		if (x == y)continue;
		X2.val[++num] = e[i].z;
		X2.add(num, x); X2.add(num, y);
		X2.fa[x][0] = num; X2.fa[y][0] = num;
		fa[x] = num; fa[y] = num;
		if (num - n == n - 1)break;
	}
	X2.dfs(find(1));
}
void Insert(int pre, int &k, int l, int r, int pos)
{
	k = ++cnt;
	siz[k] = siz[pre] + 1;
	if (l == r)return;
	int mid = (l + r) >> 1;
	if (pos <= mid)rson[k] = rson[pre], Insert(lson[pre], lson[k], l, mid, pos);
	else lson[k] = lson[pre], Insert(rson[pre], rson[k], mid + 1, r, pos);
}
int ask(int pre, int k, int l, int r, int x, int y)
{
	if (x <= l && r <= y)return siz[k] - siz[pre];
	int mid = (l + r) >> 1, res = 0;
	if (x <= mid)res += ask(lson[pre], lson[k], l, mid, x, y);
	if (mid + 1 <= y)res += ask(rson[pre], rson[k], mid + 1, r, x, y);
	return res;
}
int main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d", &x, &y); ++x; ++y;
		e[i].x = x; e[i].y = y;
	}
	klske();
	for (int i = 1; i <= (n << 1); ++i)
		if (X1.nfd[i] <= n)Insert(root[i - 1], root[i], 1, n << 1, X2.dfn[X1.nfd[i]]);
		else root[i] = root[i - 1];
	while (q--)
	{
		scanf("%d%d%d%d", &s, &t, &l, &r); ++s; ++t; ++l; ++r;
		s = X1.find(s, l, 1); t = X2.find(t, r, 2);
		puts(ask(root[X1.dfn[s] - 1], root[X1.dfn[s] + X1.siz[s] - 1], 1, n << 1, X2.dfn[t], X2.dfn[t] + X2.siz[t] - 1) ? "1" : "0");
	}
	return 0;
}