선생님께서 오늘 간식으로 피자를 시키신다. 선생님이 시킬 피자는 N가지 토핑을 선택할 수 있다. 예를 들어, ㅇㅇ피자의 경우 감자, 파인애플, 페퍼로니, 불고기, 해물 등의 토핑이 있다.

 

이론적으로는 각 토핑을 선택하거나 말거나의 경우를 모두 따지면 2^N가지 조합이 가능하지만 특 정한 종류의 두 토핑에 대해서는 궁합이 안 맞는다. 예를 들어, 파인애플과 불고기의 조합은 별로 좋지 않 다. ㅇㅇ피자의 경우 총 M쌍의 조합을 권장하지 않는다.

 

선생님은 학생들에게 최대한 많은 종류의 피자를 먹게 하고 싶어한다. 하지만 조합에 맞지 않는 피 자는 시킬 수 없다. 선생님을 도와 몇 종류의 피자를 시킬 수 있는지 구하는 프로그램을 작성하여라.

 

첫 번째 줄에 N, M이 주어진다. (1 ≤ N ≤ 20, 1 ≤ M ≤ 400) 두 번째 줄부터 M개의 줄에는 조합이 맞지 않는 두 토핑의 번호 A, B가 주어진다. (1 ≤ A, B ≤ N) 어떤 두 토핑의 조합 (A, B)가 여러 번 나타날 수 있음에 유의하여라.

첫 번째 줄에 피자 토핑을 고르는 방법의 수를 출력한다.

3 2 
1 2 
2 3

5

3 0

8

3 3
1 2
1 3
2 3

4