Coin Collectors#3152
Programmer Grisha collects coins. He has a collection of different coins, numbered from to . Grisha's friend Sasha wants to borrow some coins, but he is particular—even about coins: Sasha considers pairs of coins to be incompatible for aesthetic reasons.
Help Sasha determine in how many ways he can borrow , , , or different coins from Grisha such that no two borrowed coins are incompatible.
For example, if Grisha owns coins and Sasha considers pairs of these coins incompatible: and , Sasha can borrow any single coin ( ways), or he can borrow the pair and (as any other pair will include incompatible coins). Borrowing all three coins is not possible as that set contains incompatible pairs. So, in this case, Sasha can borrow coins in ways.
The first line contains (1 \leq K \leq 5000) — the number of Grisha's coins. Each coin is numbered from to .
The second line contains (0 \leq N \leq 5000) — the number of incompatible pairs.
Next, pairs of integers (r_1, r_2) are given, describing incompatible pairs of coins. It is guaranteed that r_1 \ne r_2 and all pairs are distinct.
Output a single integer — the total number of ways Sasha can borrow coins from Grisha.
Example 1