모든 팀이 참가하는 플레이오프

Minato Mirai 축구 협회는 매년 단일 라운드 로빈 방식으로 챔피언십을 개최하며, 각 팀은 다른 모든 팀과 한 경기씩 치른다. 다른 많은 축구 라운드 로빈 대회와 달리 이 대회에서는 무승부가 나오지 않는다. 정규 시간이 무승부면 연장전을 치르고, 연장전도 무승부면 승부차기로 승패를 가린다.

라운드 로빈에서 가장 많은 경기를 승리한 팀이 둘 이상이면 그 팀들끼리 플레이오프를 치러 우승팀을 정한다. 그러나 팀 수가 홀수이면 모든 팀의 승패 수가 같아질 수 있는데, 이 경우 모든 팀이 플레이오프에 참가하며 이를 여기서는 "풀 플레이오프"라고 부른다.

지금까지 일부 경기가 이미 치러졌고 그 결과를 알고 있다. 풀 플레이오프가 필요한지 여부는 남은 경기의 결과에 따라 달라질 수 있다. 남은 경기의 승패 조합 중 풀 플레이오프가 필요한 경우의 수를 계산하는 프로그램을 작성하시오.

Sample Input의 첫 번째 데이터셋은 5개 팀의 라운드 로빈에서 처음 세 경기의 결과이며, 다음 표와 같다. 표에서 회색 칸은 아직 치르지 않은 경기를 나타낸다.

이 경우 모든 팀이 같은 수의 경기를 승리하며, 풀 플레이오프가 필요한 남은 경기의 승패 조합은 아래와 같이 두 가지뿐이다. 두 표에서 차이는 연한 노란색으로 표시했다.

입력은 여러 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식이다.

n
m
x1 y1
...
xm ym

n은 대회에 참가하는 팀 수를 나타내는 홀수 정수로 3, 5, 7, 9 중 하나이다. m은 이미 끝난 경기 수를 나타내는 양의 정수로 n(n−1)/2보다 작다. xi와 yi는 이미 치러진 i번째 경기의 결과로, 팀 xi가 팀 yi를 이겼음을 나타낸다. xi와 yi는 각각 팀 번호를 나타내는 1 이상 n 이하의 정수이다. 어떤 팀도 자기 자신과 경기하지 않으므로 모든 i에 대해 xi ≠ yi이다. 같은 팀 조합의 경기 결과는 최대 한 번만 나타난다. 즉 i ≠ j이면 (xi,yi) ≠ (xj,yj)이고 (xi,yi) ≠ (yj,xi)이다.

입력의 끝은 0을 포함한 한 줄로 나타낸다. 데이터셋의 수는 100을 넘지 않는다.

각 데이터셋마다 풀 플레이오프가 필요하게 되는 미래의 승패 조합 수를 나타내는 정수를 한 줄에 출력한다.