You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题为交互题，但在此请提交完整程序。

题目描述

在日本的茨城县内共有 $N$ 个城市和 $M$ 条道路。这些城市是根据人口数量的升序排列的，依次编号为 $0$ 到 $N - 1$。每条道路连接两个不同的城市，并且可以双向通行。由这些道路，你能从任意一个城市到另外任意一个城市。

你计划了 $Q$ 个行程，这些行程分别编号为 $0$ 至 $Q - 1$。第 $i(0 \leq i \leq Q - 1)$ 个行程是从城市 $S_i$ 到城市 $E_i$。

你是一个狼人。你有两种形态：人形和狼形。在每个行程开始的时候，你是人形。在每个行程结束的时候，你必须是狼形。在行程中，你必须要变身（从人形变成狼形）恰好一次，而且只能在某个城市内（包括可能是在 $S_i$ 或 $E_i$ 内）变身。

狼人的生活并不容易。当你是人形时，你必须避开人少的城市，而当你是狼形时，你必须避开人多的城市。对于每一次行程 $i(0 \leq i \leq Q - 1)$，都有两个阈值 $L_i$ 和 $R_i(0 \leq L_i \leq R_i \leq N - 1)$，用以表示哪些城市必须要避开。准确地说，当你是人形时，你必须避开城市 $0, 1, \ldots , L_i - 1$ ；而当你是狼形时，则必须避开城市 $R_i + 1, R_i + 2, \ldots , N - 1$。这就是说，在行程 $i$ 中，你必须在城市 $L_i, L_i + 1, \ldots , R_i$ 中的其中一个城市内变身。

你的任务是，对每一次行程，判定是否有可能在满足上述限制的前提下，由城市 $S_i$ 走到城市 $E_i$。你的路线可以有任意长度。

输入格式

输入的第一行包含三个正整数 $N, M, Q$，其意义见题目描述。

接下来 $M$ 行，每行包含两个非负整数。在这 $M$ 行中，第 $j$ 行的两个非负整数分别表示 $X_{j - 1}, Y_{j - 1}$，即编号为 $j - 1$ 的道路连接的两个城市的编号。

接下来 $Q$ 行，每行包含四个非负整数。在这 $Q$ 行中，第 $i$ 行的四个非负整数分别表示 $S_{i - 1}, E_{i - 1}, L_{i - 1}, R_{i - 1}$，即编号为 $i - 1$ 的行程的起点城市编号、终点城市编号以及两个阈值。

输出格式

输出包含 $Q$ 行，每行包含一个非 $0$ 即 $1$ 的整数。第 $i$ 行的整数表示对于编号为 $i - 1$ 的行程，是否能从城市 $S_{i - 1}$ 走至城市 $E_{i - 1}$，若能够，那么输出整数为 $1$；若不能，那么输出整数为 $0$。

6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4

1
0
0

10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9

1
1
1
0
1
1
0
1
0
1

提示

限制条件

• $2 \leq N \leq 200, 000$
• $N - 1 \leq M \leq 400, 000$
• $1 \leq Q \leq 200, 000$
• 对于每个 $0 \leq j \leq M - 1$
  • $0 \leq X_j \leq N - 1$
  • $0 \leq Y_j \leq N - 1$
  • $X_j \neq Y_j$
• 你可以通过道路由任意一个城市去另外任意一个城市。
• 每一对城市最多只由一条道路直接连起来。换言之，对于所有 $0 \leq j < k \leq M - 1$，都有 $(X_j, Y_j) \neq (X_k, Y_k)$ 和 $(Y_j, X_j) \neq (X_k, Y_k)$
• 对于每个 $0 \leq i \leq Q - 1$
  • $0 \leq L_i \leq S_i \leq N - 1$
  • $0 \leq E_i \leq R_i \leq N - 1$
  • $S_i \neq E_i$
  • $L_i \leq R_i$

子任务

• 1.（7 分）$N \leq 100$，$M \leq 200$，$Q \leq 100$。
• 2.（8 分）$N \leq 3, 000$，$M \leq 6, 000$，$Q \leq 3, 000$。
• 3.（34 分）$M = N - 1$ 且每个城市最多与两条路相连（所有城市是以一条直线的形式连起来）。
• 4.（51 分）没有附加限制。