問題文

サイバーエージェントの社員の間では、クロスワードが流行っています。

今回作ろうとしているのは、$2$ 行 $2$ 列の $4$ マスに文字を一つずつ入れ、各行を左から読んだとき、および各列を上から読んだ時に、 いずれも単語となるものです。ただし、文字の種類が多いので、この問題では一つの整数が一つの文字に対応しているものとします。

あなたは、文字の種類数 $N$ と辞書に載っている $M$ 個の単語が与えられます。 それぞれの文字は便宜上、 $1$ から $N$ の整数で表されます。 辞書は $M$ 行からなり、そのうち $i$ 行目 $(1 \\leq i \\leq M)$ には、整数 $a_i$ と $b_i$ が書かれています。 これは、$1$ 文字目が $a_i$ で $2$ 文字目が $b_i$ である単語が存在することを意味しています。 同じ単語が辞書に複数回登場することはありません。

今、マスには何も書かれていないので、それぞれの文字を入れた時、各行各列を読んだときいずれも存在する単語となるようにしたいです。 ありうる文字の入れ方の総数を求めてください。ただし、同じ単語を複数回使用してもかまいません。

制約

• $1 \\leq N \\leq 300$
• $1 \\leq M \\leq N \\times N$
• $1 \\leq a_i, b_i \\leq N$ $(1 \\leq i \\leq M)$
• $(a_i, b_i) \\neq (a_j, b_j)$ $(1 \\leq i < j \\leq M)$

入力

入力は以下の形式で与えられる。

$N$ $M$ $a_1$ $b_1$ : $a_M$ $b_M$

出力

文字の入れ方の総数を出力せよ。

入力例 1

3 4
1 2
2 1
3 1
2 3

出力例 1

5

ありうる文字の入れ方は、下図のように $5$ 通りあります。

入力例 2

4 10
1 1
1 2
1 3
2 1
2 2
2 4
3 3
3 4
4 1
4 3

出力例 2

47