APIO 2018- 마라톤 > 문제은행 : 정보올림피아드&알고리즘




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).

 



출처

APIO 2018

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP