Baltic OI '11 P2 - Ice Cream

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type
Baltic Olympiad in Informatics: 2011 Day 1, Problem 2

Rasmus and his friends are on vacation in Italy. Since they are suffering from the heat, they decide to buy some ice cream. There are N flavors of ice cream available; flavors are numbered from 1 to N. However, some pairings of flavors should be avoided; otherwise, the taste would be unpleasant. Rasmus wants to know how many ways there are to choose three different flavors without any such impossible pairing. The order of flavors is not taken into account.

Constraints

1 \le N \le 200

0 \le M \le 10\,000

Input Specification

The first line of input contains two non-negative integers N and M, the number of flavors and the number of impossible pairings. Each of the M following lines describes an impossible pairing and contains two different flavor numbers. No impossible pairing will appear twice.

Output Specification

The first and only line of output must contain a single integer: the number of possible choices.

Sample Input

5 3
1 2
3 4
1 3

Sample Output

3

Explanation for Sample

There are 5 flavors and 3 impossible pairings. Flavor 1 should be combined with neither flavor 2 nor flavor 3, and flavor 3 also should not be chosen together with flavor 4. Only 3 ways to choose three different flavors remain: (1, 4, 5), (2, 3, 5), and (2, 4, 5).


Comments

There are no comments at the moment.