AT_bcu30_c クロスワード
题目描述
在 CyberAgent 的员工之间，填字游戏非常流行。
这次要制作的填字游戏是一个 $2$ 行 $2$ 列的 $4$ 格，每个格子中放入一个字符，使得每一行从左到右读、每一列从上到下读时，都能组成一个合法的单词。由于字符种类较多，本题中我们用整数来代表每个字符。
现在给定字符的种类数 $N$，以及字典中收录的 $M$ 个单词。每个字符用 $1$ 到 $N$ 的整数表示。字典包含 $M$ 行，第 $i$ 行 $(1 \leq i \leq M)$ 给出整数 $a_i$ 和 $b_i$，表示以 $a_i$ 为第一个字符、$b_i$ 为第二个字符的一个合法单词。字典中不会有重复单词。
初始时所有格子为空，你要按照上述规则——每一行和每一列读出的序列都能在字典中找到——统计所有可能的字符填入方式总数。允许同一个单词在行和列中重复使用。
输入格式
输入按以下格式给出：
> $N$ $M$
> $a_1$ $b_1$
> $\vdots$
> $a_M$ $b_M$
输出格式
输出所有可能的字符填入方式的总数。
说明/提示
## 限制条件
- $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)$
## 样例解释 1
所有可能的字符填入方式如下图所示，共有 $5$ 种。 
由 ChatGPT 5 翻译