题目背景
本题为交互题，但在此请提交完整程序。
题目描述
在日本的茨城县内共有 N 个城市和 M 条道路。这些城市是根据人口数量的升序排列的，依次编号为 0 到 N−1。每条道路连接两个不同的城市，并且可以双向通行。由这些道路，你能从任意一个城市到另外任意一个城市。
你计划了 Q 个行程，这些行程分别编号为 0 至 Q−1。第 i(0≤i≤Q−1) 个行程是从城市 Si 到城市 Ei。
你是一个狼人。你有两种形态：人形和狼形。在每个行程开始的时候，你是人形。在每个行程结束的时候，你必须是狼形。在行程中，你必须要变身（从人形变成狼形）恰好一次，而且只能在某个城市内（包括可能是在 Si 或 Ei 内）变身。
狼人的生活并不容易。当你是人形时，你必须避开人少的城市，而当你是狼形时，你必须避开人多的城市。对于每一次行程 i(0≤i≤Q−1)，都有两个阈值 Li 和 Ri(0≤Li≤Ri≤N−1)，用以表示哪些城市必须要避开。准确地说，当你是人形时，你必须避开城市 0,1,…,Li−1 ；而当你是狼形时，则必须避开城市 Ri+1,Ri+2,…,N−1。这就是说，在行程 i 中，你必须在城市 Li,Li+1,…,Ri 中的其中一个城市内变身。
你的任务是，对每一次行程，判定是否有可能在满足上述限制的前提下，由城市 Si 走到城市 Ei。你的路线可以有任意长度。
输入格式
输入的第一行包含三个正整数 N,M,Q，其意义见题目描述。
接下来 M 行，每行包含两个非负整数。在这 M 行中，第 j 行的两个非负整数分别表示 Xj−1,Yj−1，即编号为 j−1 的道路连接的两个城市的编号。
接下来 Q 行，每行包含四个非负整数。在这 Q 行中，第 i 行的四个非负整数分别表示 Si−1,Ei−1,Li−1,Ri−1，即编号为 i−1 的行程的起点城市编号、终点城市编号以及两个阈值。
输出格式
输出包含 Q 行，每行包含一个非 0 即 1 的整数。第 i 行的整数表示对于编号为 i−1 的行程，是否能从城市 Si−1 走至城市 Ei−1，若能够，那么输出整数为 1；若不能，那么输出整数为 0。
输入输出样例
输入样例 #1
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
输入样例 #2
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
输出样例 #2
说明/提示
限制条件
- 2≤N≤200,000
- N−1≤M≤400,000
- 1≤Q≤200,000
- 对于每个 0≤j≤M−1
- 0≤Xj≤N−1
- 0≤Yj≤N−1
- Xj=Yj
- 你可以通过道路由任意一个城市去另外任意一个城市。
- 每一对城市最多只由一条道路直接连起来。换言之，对于所有 0≤j<k≤M−1，都有 (Xj,Yj)=(Xk,Yk) 和 (Yj,Xj)=(Xk,Yk)
- 对于每个 0≤i≤Q−1
- 0≤Li≤Si≤N−1
- 0≤Ei≤Ri≤N−1
- Si=Ei
- Li≤Ri
子任务
- 1.（7 分）N≤100，M≤200，Q≤100。
- 2.（8 分）N≤3,000，M≤6,000，Q≤3,000。
- 3.（34 分）M=N−1 且每个城市最多与两条路相连（所有城市是以一条直线的形式连起来）。
- 4.（51 分）没有附加限制。