문제
선생님께서 오늘 간식으로 피자를 시키신다. 선생님이 시킬 피자는 N가지 토핑을 선택할 수 있다. 예를 들어, ㅇㅇ피자의 경우 감자, 파인애플, 페퍼로니, 불고기, 해물 등의 토핑이 있다.
이론적으로는 각 토핑을 선택하거나 말거나의 경우를 모두 따지면
선생님은 학생들에게 최대한 많은 종류의 피자를 먹게 하고 싶어한다. 하지만 조합에 맞지 않는 피자는 시킬 수 없다. 선생님을 도와 몇 종류의 피자를 시킬 수 있는지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 N, M이 주어진다. (1 ≤ N ≤ 20, 1 ≤ M ≤ 400) 두 번째 줄부터 M개의 줄에는 조합이 맞지 않는 두 토핑의 번호 A, B가 주어진다. (1 ≤ A, B ≤ N) 어떤 두 토핑의 조합 (A, B)가 여러 번 나타날 수 있음에 유의하여라.
출력
첫 번째 줄에 피자 토핑을 고르는 방법의 수를 출력한다.
예제1
입력
32
12
23
출력
5
예제2
입력
30 출력
8
예제3
입력
33
12
13
23
출력
4
출처
COCI 2015/2016 contest2 2