008 - 全チームによるプレーオフ

みなとみらいサッカー連盟が例年主催する選手権は， 参加各チームが他の全チームと 1 試合ずつを行う総当たりリーグ戦で競われる． 他の多くの総当たり形式の大会と違って，この選手権の各試合に引分はない． 規定時間内に決着がつかなければ延長戦， それでも同点ならペナルティキック戦で必ず勝者を決める．

総当たりリーグ戦で勝利数が最多だったチームが複数あれば， そのチーム間で決定戦を行って優勝チームを決める． しかし，チーム数が奇数だったら，全チームが勝敗同数で， 全チームが優勝決定戦に進む可能性もある． ここではこれを「全プレーオフ」と呼ぶ．

今，大会の試合の一部は終わっていて，その勝敗がわかっている． 全プレーオフになるかどうかは残り試合の勝敗にかかっているかもしれない． 全プレーオフになる残り試合の勝敗の組合せパターン数を求めるプログラムを作成せよ．

Sample Input の最初のデータセットは， 次の表のとおりの 5 チームによる総当たり戦の最初の 3 試合の結果を表している． 表中で灰色のセルは未実施の対戦を表している．

	Team1	Team2	Team3	Team4	Team5
Team1				lost	lost
Team2			lost
Team3		won
Team4	won
Team5	won

この場合， 全チームが同勝利数になって全プレーオフになるような残り試合の勝敗の組合せパターンは 以下に示す 2 つだけである． 2 つの表中での違いは黄色で示されている．

	Team1	Team2	Team3	Team4	Team5
Team1		won	won	lost	lost
Team2	lost		lost	won	won
Team3	lost	won		won	lost
Team4	won	lost	lost		won
Team5	won	lost	won	lost

	Team1	Team2	Team3	Team4	Team5
Team1		won	won	lost	lost
Team2	lost		lost	won	won
Team3	lost	won		lost	won
Team4	won	lost	won		lost
Team5	won	lost	lost	won

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

n
m
x₁ y₁
...
x_m y_m

n は 3, 5, 7, 9 のいずれかの奇数で，選手権の参加チーム数を表す． m は既に行われた試合数を表す正の整数であり，n(n−1)/2 より小さい． x_i, y_i は既に行われた i 番目の試合結果であり， チーム x_i がチーム y_i を破ったことを表す． x_i と y_i は， それぞれ 1 以上 n 以下の整数であり，チーム番号を示している． 自チームとの試合はないので， すべての i について x_i ≠ y_i が成り立つ． また，同じ 2 チームの間の試合結果が入力に複数回現れることはない． すなわち i ≠j ならば (x_i,y_i)≠ (x_j,y_j) かつ (x_i,y_i)≠ (y_j,x_j) である．

入力の終わりは，1 個のゼロからなる行で表される． データセットの総数は 100 を超えない.

各データセットに対し，全プレーオフになる今後の勝敗の組合せ数を 1 行に出力せよ．

5
3
3 2
4 1
5 1
3
1
1 2
3
2
1 2
3 2
5
4
4 1
4 2
5 1
5 2
5
3
4 1
4 2
5 1
5
4
3 2
4 1
5 1
5 2
9
11
6 1
6 4
7 2
7 3
7 4
8 2
8 3
8 4
9 1
9 3
9 5
9
10
6 1
6 4
7 2
7 3
7 4
8 2
8 3
8 4
9 1
9 3
5
6
4 3
2 1
5 1
2 4
1 3
2 3
9
1
1 2
0

2
1
0
0
1
0
0
16
0
1615040