20723번 - SSB Tournament 다국어

문제

Aditya is organizing a huge tournament to play the new hit video game Super Slam Battle (SSB). However, rather than the classic 1ドル$ vs 1ドル$ games, he wants to introduce some chaos into the matches by having 3ドル$ players in every game. He has recruited $n$ people to come participate in the tournament. Now, some of the contestants know each other from before so if they are in the same game, they will only play with each other if the competitive rule set is used. If two contestants do not know each other from before, then they will only play with each other if the casual rule set is used. Thus, Aditya realizes that he can only organize a game between 3ドル$ participants if they all knew each other before or if they all did not know each other before. Given $k$ pairs of people that knew each other before the tournament, help Aditya figure out the total number of games that he can organize.

입력

The first line consists of two space-separated integers $n$ and $k,ドル the number of people in the tournament and the number of pairs of people that knew each other before respectively, with 3ドル \leq n \leq 10^6$ and 1ドル \leq k \leq 10^6$. Each of the next $k$ lines contain two space-separated integers $u$ and $v$ (1ドル \leq u,v \leq n$ and $u \neq v$), signifying two people $u$ and $v$ that know each other before the tournament. Each pair $(u, v)$ will be specified at most once.

출력

Print the number of distinct games with 3ドル$ people that Aditya can organize.

제한

힌트