Fight Against Traffic

작은 도시 Nsk는 n개의 교차로와 이들을 연결하는 m개의 양방향 도로로 이루어져 있다. 각 도로는 서로 다른 두 교차로를 연결하며, 같은 교차로 쌍을 연결하는 도로는 둘 이상 존재하지 않는다. 이 도로들을 통해 임의의 교차로에서 다른 임의의 교차로로 이동할 수 있다. 두 교차로 사이의 거리는 두 교차로 사이의 경로에 포함되는 도로 수의 가능한 최솟값과 같다.

교통 체계를 개선하기 위해 시의회는 시장에게 새 도로 하나를 건설하도록 요청한다. 문제는 시장이 막 훌륭한 새 차를 샀고, 교차로 s 근처에 있는 자신의 집에서 교차로 t 근처에 있는 직장까지 운전하는 것을 매우 즐긴다는 것이다. 따라서 그는 이 두 교차로 사이의 거리가 줄어들지 않도록 새 도로를 건설하고 싶어 한다t

서로 도로로 연결되어 있지 않은 교차로 쌍 중, 두 교차로 사이에 새 도로를 건설해도 s와 t 사이의 거리가 줄어들지 않는 교차로 쌍의 수를 계산해야 한다t

입력의 첫 줄에는 정수 n, m, s, t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t)가 주어진다. 이는 각각 Nsk의 교차로 수와 도로 수, 그리고 시장의 집과 직장이 있는 교차로의 번호이다. 이어지는 m개 줄의 i-th에는 두 정수 ui와 vi (1 ≤ ui, vi ≤ n, ui ≠ vi)가 주어지며, 이는 이 도로가 교차로 ui와 vi를 직접 연결한다는 뜻이다. 임의의 두 교차로 사이에 경로가 존재하며, 같은 교차로 쌍을 연결하는 도로는 둘 이상 존재하지 않음이 보장된다.

직접 도로로 연결되어 있지 않은 교차로 쌍 중, 두 교차로 사이에 도로를 건설해도 교차로 s와 t 사이의 거리가 줄어들지 않는 쌍의 수를 나타내는 정수 하나를 출력한다t