O - Shortest Distance Query Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

N 頂点 M 辺の単純連結無向グラフが与えられます。ここで、M ≤ N + 10 です。
頂点には 1, 2, \dots, N の、辺には 1, 2, \dots, M の番号がついており、辺 i は頂点 a_i と頂点 b_i の間を結びます。 全ての辺の長さは 1 です。

Q 個のクエリを順番に処理してください。i 番目のクエリの内容は以下の通りです。

  • 整数 u_i, v_i が与えられる。頂点 u_i と頂点 v_i の間の最短距離を出力する。

制約

  • 入力は全て整数
  • 2 ≤ N ≤ 10^5
  • N - 1 ≤ M ≤ N + 10
  • 1 ≤ a_i < b_i ≤ N
  • i ≠ j ならば (a_i, b_i) ≠ (a_j, b_j)
  • 与えられるグラフは連結
  • 1 ≤ Q ≤ 10^4
  • 1 ≤ u_i < v_i ≤ N

入力

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

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M
Q
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q

出力

問題文の指示に従って Q 個の整数を改行区切りで出力せよ。

入力例 1

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

出力例 1

2
4
1

与えられるグラフは以下のようになっています。

したがって、

  • 頂点 4 と頂点 6 の間の最短距離は 2
  • 頂点 1 と頂点 5 の間の最短距離は 4
  • 頂点 1 と頂点 2 の間の最短距離は 1

となります。

入力例 2

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

出力例 2

3
3
2
4
1
1
1
4

入力例 3

11 12
6 10
9 10
8 11
3 5
1 8
7 9
2 6
3 6
4 7
3 10
1 7
1 2
6
7 10
3 8
4 7
5 9
4 5
5 10

出力例 3

2
4
1
3
5
2

Score : 6 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are given an simple connected undirected graph, where M ≤ N + 10. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M. Edge i connects Vertex a_i and Vertex b_i. The length of every edge is 1.

Process Q queries in order. The i-th query is as follows:

  • given integers u_i and v_i, find the shortest distance between Vertex u_i and Vertex v_i.

Constraints

  • All values in input are integers.
  • 2 ≤ N ≤ 10^5
  • N - 1 ≤ M ≤ N + 10
  • 1 ≤ a_i < b_i ≤ N
  • (a_i, b_i) ≠ (a_j, b_j) for i ≠ j
  • The given graph is connected.
  • 1 ≤ Q ≤ 10^4
  • 1 ≤ u_i < v_i ≤ N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M
Q
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q

Output

Print Q integers as specified in Problem Statement, each in its own line.

Sample Input 1

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

Sample Output 1

2
4
1

The given graph is as follows:

Thus,

  • the shortest distance between Vertex 4 and Vertex 6 is 2;
  • the shortest distance between Vertex 1 and Vertex 5 is 4;
  • the shortest distance between Vertex 1 and Vertex 2 is 1.

Sample Input 2

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

Sample Output 2

3
3
2
4
1
1
1
4

Sample Input 3

11 12
6 10
9 10
8 11
3 5
1 8
7 9
2 6
3 6
4 7
3 10
1 7
1 2
6
7 10
3 8
4 7
5 9
4 5
5 10

Sample Output 3

2
4
1
3
5
2