问题描述

在CyberAgent公司的员工中，兴起了填字游戏的热潮。

这次要做的是，在一个2行2列、共4个方格中，分别填入一个字符，使得从左到右和从上到下的每一行和每一列都构成一个单词。由于字符种类很多，因此在这个问题中，一个整数对应一个字符。

给定字符的种类数目 N 和包含在字典中的 M 个单词。每个字符被表示为从 1 到 N 的整数。字典由 M 行组成，第 i 行（1 ≤ i ≤ M）包含整数 ai 和 bi。这意味着存在一个单词，第一个字母是 ai，第二个字母是 bi。同一个单词不会出现多次在字典中。

现在，由于方格中没有填写任何内容，希望在填入每个字符时，使得从左到右和从上到下的每一行和每一列都是存在的单词。请计算可能的字符填法总数。可以多次使用相同的单词。

约束条件

• $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