D - Roadway Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

町 1,2, \ldots, N の N 個の町がこの順に一列に並んでいます。

また、隣り合う町どうしを結ぶ N-1 本の道があり、道 j\,(1\leq j \leq N-1) は町 j と町 j+1 を結んでいます。あなたは各道 j について、強さ w_j（非負とは限らない整数）を設定することができます。

人が道を通るとその人の体力が変化します。具体的には、体力が x の人が道 j を通ると、体力が x+w_j に変化します。

M 人の人がこれから町の間を移動します。

人 i\,(1\le i\le 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\le k\le Q) 番目のクエリでは、人 L_k, L_k + 1, \ldots , R_k の要求を全て満たすように道の強さを設定する方法がある場合 Yes を、ない場合 No を出力してください。

制約

  • 3 \le N \le 4 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le S_i, T_i \le N
  • |S_i-T_i|>1
  • (S_i, T_i) \neq (S_j, T_j)\,(i\neq j)
  • 1\le L_k\le R_k \le M
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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 行目には、人 L_k, L_k + 1, \ldots , R_k の要求を全て満たすように道の強さを設定する方法がある場合 Yes を、ない場合 No を出力せよ。

入力例 1

5 4 2
4 2
1 3
3 5
2 4
1 3
2 4

出力例 1

Yes
No

1 番目のクエリで、道 1, 2, 3, 4 の強さをそれぞれ 1, -1, 1, -1 に設定した時を考えます。

このとき、人 1 は体力 0 の状態で町 4 を出発し、体力 1 の状態で町 3 を訪れ、体力 0 の状態で町 2 に到着します。

人 2 は体力 0 の状態で町 1 を出発し、体力 1 の状態で町 2 を訪れ、体力 0 の状態で町 3 に到着します。

人 3 は体力 0 の状態で町 3 を出発し、体力 1 の状態で町 4 を訪れ、体力 0 の状態で町 5 に到着します。

よってこの設定方法は人 1,2,3 の要求をすべて満たすので、 1 行目には Yes を出力します。

2 番目のクエリでは、人 2, 3, 4 の要求をすべて満たすことは不可能なので No を出力します。

入力例 2

7 6 3
1 5
2 4
4 6
7 1
5 3
1 6
1 6
4 4
2 5

出力例 2

No
Yes
Yes

Score : 900 points

Problem Statement

There are N towns, numbered 1,2,\ldots,N, arranged in a line in this order.

There are N-1 roads connecting adjacent towns: road j\,(1 \leq j \leq N-1) connects towns j and j+1. For each road j, you can set a strength w_j (an integer that may be negative).

When a person travels along a road, their stamina changes. Specifically, if a person with stamina x travels along road j, their stamina becomes x + w_j.

There are M people who will now move between these towns.

Person i\,(1 \le i \le M) starts with stamina 0 at town S_i and travels to town T_i via the shortest path. It is guaranteed that |S_i - T_i| > 1. Also, (S_i, T_i) \neq (S_j, T_j) if i \neq j.

Person i’s requirement is as follows:

When departing Town S_i and when arriving at Town T_i, their stamina should be exactly 0. At every other town, their stamina should always be a positive integer.

Assume that there are no changes to stamina other than those due to traveling along roads as described above.

Process Q queries. For the k-th query (1 \le k \le Q), if it is possible to set the strengths of the roads so that the requirements of all people L_k, L_k + 1, \ldots, R_k are satisfied, print Yes; otherwise, print No.

Constraints

  • 3 \le N \le 4 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le S_i, T_i \le N
  • |S_i - T_i| > 1
  • (S_i, T_i) \neq (S_j, T_j)\,(i \neq j)
  • 1 \le L_k \le R_k \le M
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines.

The k-th line should contain Yes if there is a way to set the strengths of the roads so that the requirements of all people L_k, L_k + 1, \ldots, R_k are satisfied, and No otherwise.

Sample Input 1

5 4 2
4 2
1 3
3 5
2 4
1 3
2 4

Sample Output 1

Yes
No

For the first query, consider setting the strengths of roads 1, 2, 3, 4 to 1, -1, 1, -1, respectively.

  • Person 1 starts at town 4 with stamina 0, visits town 3 with stamina 1, and arrives at town 2 with stamina 0.
  • Person 2 starts at town 1 with stamina 0, visits town 2 with stamina 1, and arrives at town 3 with stamina 0.
  • Person 3 starts at town 3 with stamina 0, visits town 4 with stamina 1, and arrives at town 5 with stamina 0.

Thus, this configuration satisfies the requirements of persons 1,2,3, so print Yes on the first line.

For the second query, it is impossible to satisfy the requirements of persons 2,3,4 simultaneously, so print No.

Sample Input 2

7 6 3
1 5
2 4
4 6
7 1
5 3
1 6
1 6
4 4
2 5

Sample Output 2

No
Yes
Yes