← 返回题目列表

AtCoder · bcu30_c

C. 填字游戏

中文机器翻译题面 查看原题

配点 : 100 点

問題文

填字游戏在 Cyber​​Agent 员工中很受欢迎。

这次我想做的是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