Minus One

이쿠타 군은 무방향 그래프에 남다른 애정을 가지고 있다. 이쿠타 군은 무방향 그래프 $G$와 그 두 점 $s,t$의 쌍 $(G,s,t)$ 중에서 "아름다움"이 큰 것을 좋아한다. 쌍 $(G,s,t)$의 "아름다움"이란, 변 $e = \{u, v\}$ ($u$와 $v$는 $G$의 서로 다른 두 점) 중에서 $G$에서 $s$에서 $t$로 가는 최단 경로의 길이가, $G$에 $e$를 추가한 무방향 그래프에서 $s$에서 $t$로 가는 최단 경로의 길이보다 1만큼 큰 것의 개수이다.

여러분의 일은 쌍 $(G,s,t)$가 주어졌을 때 그 "아름다움"을 구하는 프로그램을 작성하는 것이다.

입력은 다음 형식으로 주어진다.

$N$ $M$ $s$ $t$

$x_1$ $y_1$

...

$x_i$ $y_i$

...

$x_M$ $y_M$

처음에 무방향 그래프의 정점 수, 변 수, 두 정점을 나타내는 정수 $N,M,s,t$가 입력된다. 2행부터 $M+1$행까지는 변으로 연결된 두 정점이 입력된다. (단, $G$의 정점 집합을 $\{1,..., N\}$로 한다.)

주어진 그래프를 $G$라고 할 때, 쌍 $(G,s,t)$의 "아름다움"을 1행으로 출력하라.

입력 중 각 변수는 다음 제약을 만족한다.

• $2\leq N \leq 100,000$

• $1\leq M \leq 300,000$

• $1\leq s,t,x_i,y_i \leq N$

• $s$와 $t$는 다르다

• $s$에서 $t$로 갈 수 있음이 보장된다