hibye1217   3년 전

문제

어떤 무방향 그래프 $ G $와 두 정점 $ s, t $에 대해, ($ G, s, t $)의 아름다움은 아래 조건을 만족하는 간선 $ e $의 개수이다.

  • $ G $에 $ e $를 추가하면 $ s $에서 $ t $로 가는 최단 경로의 길이가 정확히 1 줄어든다.

무향그래프 $ G $와 두 정점 $ s, t $가 주어질 때, 이의 아름다움을 계산해보자.

입력

첫째 줄에는 $ G $의 정점 개수 $ N $과 간선 개수 $ M $, 그리고 $ s $와 $ t $가 공백을 사이에 두고 주어진다.

이후 둘째 줄부터 $ M $개의 줄에 걸쳐, 두 정수 $ v $와 $ w $가 주어진다. 이는 $ v $와 $ w $를 잇는 간선이 $ G $에 존재함을 의미한다.

($ G $의 정점에는 $ 1 $부터 $ N $까지의 번호가 매겨져 있다.)

출력

($ G, s, t $)의 아름다움을 출력한다.

제한

  • $ 2 \le N \le 100\,000 $
  • $ 1 \le M \le 300\,000 $
  • $ 1 \le s, t, v, w \le N $
  • $ s \neq t $
  • $ s $에서 출발해서 $ t $에 도달할 수 있다.

댓글을 작성하려면 로그인해야 합니다.