Informatica Online Judge

  민초 소믈리에 최승민 2 [2462 / 099E]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 38   Total Tried : 175


The Champion of this Problem (C++) : gs18051 - ms / 476byte
My Best Submission (C++) : N/A

[36th 최은수(gs18115)]
Writer ID : [gs18115]

Background

저번에 민초빙수를 먹기 위해 시내를 돌아다니던 승민이는 맛있는 민초 가게를 찾았다.

민초 가게에서는 총 N개의 민초 메뉴를 팔고 있다.

승민이는 매번 이 가게에 갈 때마다 2개의 민초를 먹는다. 그리고, 맛을 평가하여, 무엇이 더 맛있는지를 판단한다.

승민이는 절대 미각이기 때문에, a가 b보다 맛있고 b가 c보다 맛있다면 반드시 a가 c보다 맛있다고 평가하며, 두 민초에 대해서의 맛의 평가는 동일하다. 또한,

서로 다른 두 민초에 대해 맛있음의 정도가 같다고 판단을 내리지는 않는다.

승민이는 매일 한 번씩 총 T일 가게에 다녀왔다. 오늘도 민초 가게에 가려고 하는 승민이는, 이왕이면 자신이 지금까지 먹었던 결과들로 무엇이 더 맛있을지 유추할 수 없는 민초 두 메뉴를 시키려고 한다.

승민이가 민초를 주문하는 방법의 수를 구해 주자!

Input

첫 줄에 민초가게의 메뉴 수 N과 승민이가 민초 가게에 다녀온 일수인 T가 주어진다. (1 <= N <= 500, 1 <= T <= 10,000)
다음 T줄에는, 두 자연수 a와 b가 주어진다. 이는 a가 b보다 맛있었다는 뜻이다. (1 <= a, b <= N, a != b)

Output

승민이가 민초 메뉴를 주문하는 방법의 수를 출력한다.
(단, (a, b)와 (b, a)는 같은 방법으로 본다.)

IO Example

입력
4 3
1 2
3 2
2 4

출력
1

설명
승민이가 무엇이 더 맛있는지 유추할 수 없는 메뉴는 (1,3)으로 유일하다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]