Stamp Rally

AtCoder

IDagc002_d

Time2000ms

Memory256MB

Difficulty—

We have an undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects vertices $a_i$ and $b_i$. The graph is connected. On this graph, $Q$ pairs of brothers are participating in an activity called _Stamp Rally_. The Stamp Rally for the $i$\-th pair will be as follows: * One brother starts from vertex $x_i$, and the other starts from vertex $y_i$. * The two explore the graph along the edges to visit $z_i$ vertices in total, including the starting vertices. Here, a vertex is counted only once, even if it is visited multiple times, or visited by both brothers. * The score is defined as the largest index of the edges traversed by either of them. Their objective is to minimize this value. Find the minimum possible score for each pair. ## Constraints * $3≤N≤10^5$ * $N−1≤M≤10^5$ * $1≤a_i<b_i≤N$ * The given graph is connected. * $1≤Q≤10^5$ * $1≤x_j<y_j≤N$ * $3≤z_j≤N$ ## Input The input is given from Standard Input in the following format: $N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$ $Q$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ $:$ $x_Q$ $y_Q$ $z_Q$ [samples]

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "Stamp Rally",
    "description": {
      "content": "We have an undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects vertices $a_i$ and $b_i$. The grap",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc002_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have an undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects vertices $a_i$ and $b_i$. The grap...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments