NUMWAYS - Number Of ways

Tuktuk loves candies and Chotu loves to keep Tuktuk happy. Now in the candy shop there are N candies (1 to N). Now the shop owner has a list of pairs of candies that have same color. If a particular candy is not in the list, it means that it has different color from all the other candies. Now Tuktuk wants to eat three candies, all of different color. Chotu is wondering that in how many ways he can pick the candies from the shop to keep her happy. Can you help Chotu?

Input

First line of the input will contain N - Total number of candies. Each candy is assigned a number from 1 to N (2 <= N <= 1000000).

Second line of the input will contain C - Number of pairs of candies that the shop owner has.(1 <= C <= 100000).This is followed by C pairs. Each pair has two numbers C1 and C2 each where 1 <= C1 <= N and 1 <= C2 <= N and C1 != C2 .Total number of different candy colors will not exceed 1000.

Output

Number of ways in which Chotu can pick the candies.

Example

Input:
6
3
1 2
3 4
5 6

Output:
8

Chotu can pick - {1,3,5} {1,3,6} {1,4,5} {1,4,6} {2,3,5} {2,3,6} {2,4,5} {2,4,6}


Added by:Aditya Dixit
Date:2015-02-20
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.