AT_arc196_d.[ARC196D] Roadway

有 $N$ 个城镇，编号为 $1,2,\ldots,N$，这些城镇按顺序排成一列。

此外，有 $N-1$ 条道路，每条道路连接相邻的两个城镇。第 $j$ 条道路（$1\leq j\leq N-1$）连接城镇 $j$ 和城镇 $j+1$。你可以为每条道路 $j$ 设置一个强度 $w_j$（可以为负数的整数）。

当一个人通过一条道路时，他的体力会发生变化。具体来说，体力为 $x$ 的人在通过第 $j$ 条道路后，体力会变为 $x+w_j$。

接下来有 $M$ 个人要在城镇之间移动。

第 $i$ 个人（$1\leq i\leq M$）从体力为 $0$ 的状态下，从城镇 $S_i$ 出发，沿最短路径前往城镇 $T_i$。这里保证 $|S_i-T_i|>1$。另外，若 $i\neq j$，则 $(S_i,T_i)\neq (S_j,T_j)$。

第 $i$ 个人的要求如下：

当他从城镇 $S_i$ 出发和到达城镇 $T_i$ 时，体力恰好为 $0$，在其他经过的城镇时，体力始终为正整数。

此外，除了通过道路导致的体力变化外，体力不会有其他变化。

请处理 $Q$ 个询问。对于第 $k$ 个询问（$1\leq k\leq Q$），如果存在一种道路强度的设置方法，能满足第 $L_k,L_k+1,\ldots,R_k$ 个人的所有要求，则输出 Yes，否则输出 No。

输入按以下格式从标准输入给出。

$N$ $M$ $Q$
$S_1$ $T_1$
$S_2$ $T_2$
$\vdots$
$S_M$ $T_M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

输出 $Q$ 行。

第 $k$ 行输出 Yes，如果存在一种道路强度的设置方法，能满足第 $L_k,L_k+1,\ldots,R_k$ 个人的所有要求；否则输出 No。

数据范围

• $3\leq N\leq 4\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $1\leq Q\leq 2\times 10^5$
• $1\leq S_i,T_i\leq N$
• $|S_i-T_i|>1$
• $(S_i,T_i)\neq (S_j,T_j)\ (i\neq j)$
• $1\leq L_k\leq R_k\leq M$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个询问，考虑将道路 $1,2,3,4$ 的强度分别设置为 $1,-1,1,-1$。此时，第 $1$ 个人从城镇 $4$ 出发，体力为 $0$，到达城镇 $3$ 时体力为 $1$，到达城镇 $2$ 时体力为 $0$。第 $2$ 个人从城镇 $1$ 出发，体力为 $0$，到达城镇 $2$ 时体力为 $1$，到达城镇 $3$ 时体力为 $0$。第 $3$ 个人从城镇 $3$ 出发，体力为 $0$，到达城镇 $4$ 时体力为 $1$，到达城镇 $5$ 时体力为 $0$。因此，这种设置方法能满足第 $1,2,3$ 个人的所有要求，所以第 $1$ 行输出 Yes。对于第 $2$ 个询问，不可能满足第 $2,3,4$ 个人的所有要求，因此输出 No。

由 ChatGPT 4.1 翻译