3257 : 마라톤
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 0 회
- 시도횟수
- 0 회
문제
지역 N개와 두 지역을 연결하는 양방향 도로 E개로 이루어진 도시가 있다. 도시의 번호는 1 이상 N 이하의 정수이다.
우리는 이 도시에서 마라톤을 개최하려고 한다. 시장은 지역 사회 발전을 위해 시작점은 s번 지역에, 반환점은 c번 지역에, 도착점은 f번 지역에 설치하려고 한다. 하지만 마라톤 코스는 s번 지역에서 시작하고 c번 지역을 지나고 f번 지역에서 끝나는 경로 중에서 같은 지역을 여러 번 지나지 않는 것을 선택해야 하므로 s, c, f를 잘못 정하면 마라톤 코스를 만들 수 없을 수도 있다.
도시의 정보가 주어지면 마라톤 코스를 만들 수 있는 (s, c, f) 쌍의 수를 구하는 프로그램을 작성하여라. s, c, f는 서로 달라야 한다.
입력형식
첫째 줄에 지역의 수 N과 도로의 수 E가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ E ≤ 200,000)
다음 E개 줄에는 도로의 정보 Ai와 Bi가 주어진다. 지역 Ai와 Bi를 연결하는 도로라는 뜻이며, Ai와 Bi는 같지 않다. 또, 두 도시를 연결하는 도로가 둘 이상인 경우는 없다.
출력형식
마라톤 코스를 만들 수 있는 (s, c, f) 쌍의 수를 구하는 프로그램을 작성하여라.
입력 예복사하기 4 3 1 2 2 3 3 4 |
출력 예복사하기 8 |
입력 예복사하기 4 4 1 2 2 3 3 4 4 2 |
출력 예복사하기 14 |
Hint!
예제 1에서 만들 수 있는 (s, c, f): (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (3, 2, 1), (4, 2, 1), (4, 3, 1), (4, 3, 2).
예제 2에서 만들 수 있는 (s, c, f): (1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 4, 3), (2, 3, 4), (2, 4, 3), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2).