Roadway

AtCoder

IDarc196_d

Time3000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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`.

Input #2

Output #2

No
Yes
Yes

API Response (JSON)

{
  "problem": {
    "name": "Roadway",
    "description": {
      "content": "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 ro",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc196_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ towns, numbered $1,2,\\ldots,N$, arranged in a line in this order.\nThere are $N-1$ roads connecting adjacent towns: road $j\\,(1 \\leq j \\leq N-1)$ connects towns $j$ and $j+1$. For each ro...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments