곰곰이의 심부름

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

곰곰이는 닭 다리를 좋아한다. 특히 두 개를 좋아하는데, 집에 갈 때마다 닭 다리를 두 개씩 사 간다. 곰곰이는 심부름이 있기 때문에 집에 가기 전, 심부름 장소를 들리고 가야 한다. 

곰곰이의 나라는 NN개의 도시로 이루어져 있고, N1N-1개의 양방향 도로로 이어져 있다. 곰곰이는 현재 SS도시에, 곰곰이의 집은 HH도시에, 심부름 장소는 CC도시에 있다. 곰곰이의 나라는 연결그래프이다.

곰곰이는 현재 도시 - 심부름 도시 - 집 도시의 최단 경로로 이동할 것이다. 곰곰이는 각 도시에서 최대 한 개의 닭 다리를 살 수 있다. 곰곰이는 집에 도착했을 때, 닭 다리가 정확히 두 개 있어야 한다. 곰곰이는 노트에 자신이 닭 다리를 산 도시의 순서쌍을 적어둔다. 예를 들어 33번 도시에서 닭 다리를 산 뒤, 11번 도시에서 닭 다리를 샀으면 (3,1)(3, 1)로 표기한다. 만들어질 수 있는 순서쌍의 개수를 구해보자.

입력

첫째 줄에 도시의 개수 N(1N100,000)N (1 \leq N \leq 100\\,000)이 주어진다.

둘째 줄에 곰곰이의 현재 도시 SS, 심부름 도시 CC, 집 도시 HH가 공백으로 구분되어 주어진다. (1S,C,H N)(1 \leq S, C, H \leq N)

N1N-1줄에 거쳐 도로로 연결된 두 도시 u,vu, v가 주어진다. (1u,vN)(1 \leq u, v \leq N)

입력으로 주어지는 값은 모두 정수이다.

출력

첫째 줄에 만들어질 수 있는 순서쌍의 개수를 출력한다.