Coin Collectors
Programmer Grisha has a collection of coins, specifically K different coins, each uniquely numbered from 1 to K. Grisha's friend Sasha wants to borrow some coins, but he is selective and has certain preferences: there are N pairs of coins that Sasha finds aesthetically incompatible.
Your task is to help Sasha figure out how many ways he can borrow 1, 2, 3, or 4 different coins from Grisha, ensuring that no two borrowed coins are incompatible.
For instance, if Grisha owns 3 coins and Sasha considers 2 pairs of these coins incompatible: (1, 2) and (2, 3), Sasha has the following options: he can borrow any single coin (3 ways), or he can borrow the pair 1 and 3 (since any other pair would be incompatible). However, borrowing all three coins is not possible because it would include incompatible pairs. Therefore, in this scenario, Sasha has 4 valid ways to borrow coins.
Input
The input begins with the number K (1 ≤ K ≤ 5000), representing the total number of coins Grisha has. Each coin is numbered from 1 to K. Next, the number N (0 ≤ N ≤ 5000) is provided, indicating the number of incompatible pairs. Following this, N pairs of integers (r_1, r_2) are listed, specifying the incompatible pairs of coins. It is guaranteed that r_1≠r_2 and all pairs are distinct.
Output
Output a single integer representing the total number of ways Sasha can borrow coins from Grisha.