Playoff by all the teams

時間制限 : 8 sec, メモリ制限 : 262144 KB
英語版はこちら

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

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

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

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

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

Team \ AgainstTeam1Team2Team3Team4Team5
Team1x  lostlost
Team2 xlost  
Team3 wonx  
Team4won  x 
Team5won   x

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

Team \ AgainstTeam1Team2Team3Team4Team5
Team1xwonwonlostlost
Team2lostxlostwonwon
Team3lostwonxwonlost
Team4wonlostlostxwon
Team5wonlostwonlostx
Team \ AgainstTeam1Team2Team3Team4Team5
Team1xwonwonlostlost
Team2lostxlostwonwon
Team3lostwonxlostwon
Team4wonlostwonxlost
Team5wonlostlostwonx

Input

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

n
m
x1 y1
...
xm ym

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

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

Output

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

Sample Input

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

Output for the Sample Input

2
1
0
0
1
0
0
16
0
1615040

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Yokohama, Japan, 2018-07-6
https://icpc.iisf.or.jp/2018-yokohama/