한윤정이 이탈리아에서 아이스크림을 고르는 방법
면접 대비시간 제한1초메모리 제한128 MB
N개의 아이스크림 중에서 금지된 쌍이 하나도 포함되지 않는 3개 조합의 개수를 구합니다.
문제
한윤정과 친구들은 방학에 이탈리아로 여행을 갔다. 날씨가 더워서 아이스크림을 먹기로 했다.
가게에는 1번부터 N번까지 번호가 붙은 아이스크림이 있다. 일부 두 종류는 함께 고르면 맛이 나빠진다.
한윤정은 맛이 나빠지는 조합을 피해서 서로 다른 아이스크림 3가지를 고르려고 한다. 가능한 선택 방법의 수를 구하라.
입력
첫째 줄에 아이스크림 종류 수 N과 함께 고르면 안 되는 조합의 수 M이 주어진다.
다음 M개 줄에는 함께 고르면 안 되는 두 아이스크림 번호가 주어진다. 같은 조합은 두 번 이상 주어지지 않는다.
1 <= N <= 2000 <= M <= 10,000
출력
가능한 선택 방법의 총개수를 출력한다.
힌트
아이스크림이 5종류이고 함께 고르면 안 되는 조합이 (1, 2), (3, 4), (1, 3)인 경우를 생각해 보자. 가능한 선택은 (1, 4, 5), (2, 3, 5), (2, 4, 5)로 3가지이다.