1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| #include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#define debag(...) void(0)
#endif
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define N 200010
int n, m, i, j, k, T;
int q, u, v;
vector<int>G1[N], G2[N];
struct Node {
int i, j, k, tot;
int F[N], f[N][21], dfn[N], L[N], R[N];
vector<int>G[N];
int fa(int x) {
if(F[x] == x) return x;
return F[x] = fa(F[x]);
}
void set() {
for(i = 1; i <= n; ++i) F[i] = i;
}
void add(int x, int y) {
if(x == fa(y)) return ;
debug("cun %d %d\n", x, fa(y));
G[x].pb(fa(y)); F[fa(y)] = x;
}
void dfs(int x) {
dfn[++tot] = x; L[x] = tot;
for(int y : G[x]) dfs(y), f[y][0] = x; R[x] = tot;
}
void work() {
for(k = 1; k <= 20; ++k)
for(i = 1; i <= n; ++i) f[i][k] = f[f[i][k - 1]][k - 1];
debug("dfn "); for(i = 1; i <= n; ++i) debug("%d ", dfn[i]); debug("\n");
}
pair<int, int> jump(int x, int lim, int op) {
for(k = 20; k >= 0; --k)
if(f[x][k]) {
if(op == 0 && f[x][k] < lim) continue;
if(op == 1 && f[x][k] > lim) continue;
x = f[x][k];
}
return {L[x], R[x]};
}
}T1, T2;
int tot, s[N << 5], ls[N << 5], rs[N << 5];
struct Segment_tree {
#define mid ((l + r) >> 1)
void add(int &k, int u, int l, int r, int x) {
if(!k) k = ++tot;
if(l == r) return ++s[k], void();
if(x <= mid) add(ls[k], ls[u], l, mid, x);
else add(rs[k], rs[u], mid + 1, r, x);
if(!ls[k]) ls[k] = ls[u]; if(!rs[k]) rs[k] = rs[u];
s[k] = s[ls[k]] + s[rs[k]];
}
int qry(int k, int l, int r, int x, int y) {
if(l >= x && r <= y) return s[k];
int sum = 0;
if(x <= mid) sum += qry(ls[k], l, mid, x, y);
if(y >= mid + 1) sum += qry(rs[k], mid + 1, r, x, y);
return sum;
}
}Seg;
int rt[N];
int a[N], b[N];
signed main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
n = read(); m = read(); q = read();
for(i = 1; i <= m; ++i) {
u = read() + 1; v = read() + 1; if(u > v) swap(u, v);
debug("%d %d\n", u, v);
G1[u].pb(v); G2[v].pb(u);
}
T1.set(); T2.set();
for(i = 1; i <= n; ++i)
for(int j : G2[i]) T1.add(i, j);
for(i = n; i >= 1; --i)
for(int j : G1[i]) T2.add(i, j);
T1.dfs(n); T2.dfs(1); T1.work(); T2.work();
for(i = 1; i <= n; ++i) b[T1.dfn[i]] = i;
for(i = 1; i <= n; ++i) a[i] = b[T2.dfn[i]];
for(i = 1; i <= n; ++i) debug("%d ", a[i]); debug("\n");
for(i = 1; i <= n; ++i) Seg.add(rt[i], rt[i - 1], 1, n, a[i]);
while(q--) {
int L, R;
u = read() + 1; v = read() + 1; L = read() + 1; R = read() + 1;
debug("(%d %d) [%d %d]\n", u, v, L, R);
if(u < L || v > R) { printf("0\n"); continue; }
auto t1 = T2.jump(u, L, 0); auto t2 = T1.jump(v, R, 1);
int l1 = t1.fi, r1 = t1.se, l2 = t2.fi, r2 = t2.se;
debug("[%d %d] [%d %d]\n", l1, r1, l2, r2);
int s = Seg.qry(rt[r1], 1, n, l2, r2) - Seg.qry(rt[l1 - 1], 1, n, l2, r2);
printf(s ? "1\n" : "0\n");
}
return 0;
}
|
