Choosing Ice Cream in Italy

Interview

Time limit1sMemory limit128 MB

Summary
Given N items and forbidden pairs, count the triples of items where no two form a forbidden pair.
Level

Easy3 of 10

Topics
Brute force, Array
Solved
No attempts yet

Problem

Han Yoonjung and her friends went to Italy during vacation. Because the weather was hot, they decided to eat ice cream.

The shop sells N kinds of ice cream, numbered from 1 to N. Some pairs of flavors taste bad when chosen together.

Yoonjung wants to choose 3 different kinds of ice cream while avoiding every bad pair. Count how many choices are possible.

Input

The first line contains the number of ice cream kinds N and the number of forbidden pairs M.

Each of the next M lines contains two ice cream numbers that must not be chosen together. The same pair is not given more than once.

  • 1 <= N <= 200
  • 0 <= M <= 10,000

Output

Print the total number of possible choices.

Hint

Suppose there are 5 kinds of ice cream and the forbidden pairs are (1, 2), (3, 4), and (1, 3). The possible choices are (1, 4, 5), (2, 3, 5), and (2, 4, 5), so there are 3 choices.

Examples1

  1. Example 1

    Input
    5 3
1 2
3 4
1 3
    Expected output
    3