Ex - Directed Graph and Query

AtCoder

IDabc287_h

Time4500ms

Memory256MB

Difficulty—

There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$\-th directed edge goes from vertex $a_i$ to vertex $b_i$. The cost of a path on this graph is defined as: * the maximum index of a vertex on the path (including the initial and final vertices). Solve the following problem for each $x=1,2,\ldots,Q$. * Find the minimum cost of a path from vertex $s_x$ to vertex $t_x$. If there is no such path, print `-1` instead. The use of fast input and output methods is recommended because of potentially large input and output. ## Constraints * $2 \leq N \leq 2000$ * $0 \leq M \leq N(N-1)$ * $1 \leq a_i,b_i \leq N$ * $a_i \neq b_i$ * If $i \neq j$, then $(a_i,b_i) \neq (a_j,b_j)$. * $1 \leq Q \leq 10^4$ * $1 \leq s_i,t_i \leq N$ * $s_i \neq t_i$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$ $Q$ $s_1$ $t_1$ $\vdots$ $s_Q$ $t_Q$ [samples]

Samples

Input #1

Output #1

2
3
-1

For $x=1$, the path via the $1$\-st edge from vertex $1$ to vertex $2$ has a cost of $2$, which is the minimum.  
For $x=2$, the path via the $2$\-nd edge from vertex $2$ to vertex $3$ and then via the $3$\-rd edge from vertex $3$ to vertex $1$ has a cost of $3$, which is the minimum.  
For $x=3$, there is no path from vertex $1$ to vertex $4$, so `-1` should be printed.

API Response (JSON)

{
  "problem": {
    "name": "Ex - Directed Graph and Query",
    "description": {
      "content": "There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$\\-th directed edge goes from vertex $a_i$ to vertex $b_i$. The cost of a path on this g",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4500,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc287_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$\\-th directed edge goes from vertex $a_i$ to vertex $b_i$.\nThe cost of a path on this g...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments