페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2498

[고등부] 2025 KOI 1차대회 대비 모의고사 (3주차)

지나치는 노드들
서브태스크
2초 1024MB

문제

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

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

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

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


입력

첫 줄에 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)

  • 모든 입력은 정수


출력

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


부분문제

번호 점수 조건
#110점

N+Q\le 10

#215점

Q=2

#320점

N \le 10

#425점

N \le 100

#530점

추가 제약 조건 없음


예제 #1

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

예제 #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
로그인해야 코드를 작성할 수 있어요.