Geppetto's Pizza

Geppetto owns a pizza shop and is determined to make the best pizzas in town. He has \(N\) ingredients (each available only once) labeled \(1\) to \(N\). However, there are \(M\) pairs of conflicting ingredients. If a pizza includes both ingredients from any conflicting pair, it will taste awful!

Your task is to count the number of different pizzas Geppetto can make such that no pizza contains a conflicting pair of ingredients. Two pizzas are considered different if there exists an ingredient \(i\) that is present in one pizza but not in the other.

inputFormat

The first line contains two integers \(N\) and \(M\). The next \(M\) lines each contain two integers \(u\) and \(v\) indicating that ingredients \(u\) and \(v\) conflict with each other.

outputFormat

Output a single integer representing the number of valid pizzas that can be made.

sample

3 2
1 2
2 3

5