¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8397
Subtarea

지나치는 노드들 2s 1024MB

Problemas

N개의 노드와 M개의 간선으로 이루어진 그래프가 있다.

각 간선은 서로 다른 두 개의 노드를 양방향으로 연결하며, x번째 간선의 가중치는 2^x이다.

하나의 노드에서 다른 모든 노드로 갈 수 있는 경로가 항상 존재하는데, 그러한 경로 중 가중치의 합이 최소로 걸리는 경로를 이용하여
(만약 그러한 경로가 여러 개라면, 거치는 노드의 수가 가장 적은 경로로) 이동할때, Q개의 질의에 응답하는 프로그램을 작성하시오.

각 질의는 두 노드의 번호가 주어지며, 하나의 노드에서 다른 노드로 이동하는 경로에서 지나치는 (시작 노드와 도착 노드가 아닌) 다른 노드의 개수를 출력하시오.


Entrada

첫 줄에 N, M이 주어진다.

이어 M줄에 걸쳐 x번째 줄에 x번째 간선으로 연결된 두 노드 A_x와 B_x가 주어진다.

그 다음 줄에 Q가 주어진다.

이어 Q줄에 걸쳐 시작 노드와 도착 노드를 의미하는 두 노드 S_y와 E_y가 주어진다.

[제한]

  • 2 \le N \le 2 \cdot 10^5

  • N-1 \le M \le 2 \cdot 10^5

  • 1 \le A_x, B_x \le N (1\le x \le N)

  • A_x \ne B_x (1\le x \le N)

  • 2 \le Q \le 2 \cdot 10^5

  • 1 \le S_y, E_y \le N (1\le y \le Q)

  • S_y \ne E_y (1\le y \le Q)

  • 모든 입력은 정수


Salida

Q개의 줄에 걸쳐 각 질의에 대한 답을 출력한다.


Subtarea

# Puntaje Condición
#110

N+Q\le 10

#215

Q=2

#320

N \le 10

#425

N \le 100

#530

추가 제약 조건 없음


Ejemplo #1

3 3
1 2
1 3
2 3
3
1 2
1 3
2 3
0
0
1

Ejemplo #2

4 4
1 2
2 3
3 4
4 1
6
1 2
1 3
1 4
2 3
2 4
3 4
0
1
2
0
1
0


Fuente

제4회 보라매컵 F번

Debes iniciar sesión para escribir código.