5089：检验零件
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 检验零件
## 题目描述
某工厂中，每个工人生产的零件都需要经过严格的检验流程。
检验流程规定，每个工人生产的零件，必须经过 **$3$ 个不同的人**检验合格之后，才能发放产品合格证书。
工厂共有 $N$ 个工人，工人的工位之间通过**双向**的传送带连接（工位编号为 $1 \sim N$ ）。
位于 $i$ 号工位的工人生产完一个零件之后，他会**立刻**通过传送带，直接传送给跟他**相邻工位的**工人进行检验。
相邻工位的工人检验完毕后，会在零件的检验标签上，标注检验结果，以及自己工位编号。然后，他会将该零件再次通过传送带，传送给相邻工位的工人进行检验。由于零件必须由 $3$ 个不同的工人检验，因此他**一定不会把零件传送给已经检验过该零件的工人**。
需要注意的是，第 $2$ 个工人检验结束后，可以将零件传送回 $i$ 号工位的工人。即：由零件的生产者作为第 $3$ 个检验人，**也是允许的**。
从编号为 $i$ 的工位开始，零件检验会形成长度为 $3$ （经过了 $3$ 条传送带）的检验路径。有意思的是，这样的路径可能不是唯一的。
比如，下图所示的工位分布图中，位于 $1$ 号工位的工人生产的零件，可以有如下 $7$ 条不同的合法检验路径。
1 2 3 1
1 3 2 1
1 2 3 5
1 3 2 5
1 2 5 3
1 3 5 2
1 3 2 4
请编程计算出，如果每个工位都需要生产一个零件，并进行检验，**所有的工位一共**能形成多少条不同的合法检验路径。
## 输入格式
第 $1$ 行输入 $2$ 个整数 $N$ 和 $M$ ，分别表示工位数量和传送带数量。
接下来 $M$ 行，每行输入两个整数 $U_i$ 和 $V_i$ ，表示 $U_i$ 号工位和 $V_i$ 号工位之间存在一条传送带，任意两个工位之间**最多**只有一条传送带。
## 输出格式
输出一个整数，表示所有工位一共能形成多少条不同的合法检验路径。
## 样例
### 样例输入 1
```text
3 3
1 2
2 3
3 1
```
### 样例输出 1
```text
6
```
### 样例输入 2
```text
5 6
1 2
1 3
2 3
2 4
2 5
3 5
```
### 样例输出 2
```text
32
```
### 样例输入 3
```text
6 6
2 1
3 2
3 4
5 2
5 6
1 6
```
### 样例输出 3
```text
16
```
## 说明/提示
样例 $1$ 解释
从每个点开始都有 $2$ 条不同的检验路径，因此共有 $6$ 条不同的检验路径。
样例 $2$ 解释
本题的题目描述中的图，对应样例 $2$ 的数据。
从 $1$ 号点开始，存在 $7$ 条检验路径。
从 $2$ 号点开始，存在 $6$ 条检验路径。
从 $3$ 号点开始，存在 $8$ 条检验路径。
从 $4$ 号点开始，存在 $4$ 条检验路径。
从 $5$ 号点开始，存在 $7$ 条检验路径。
因此，共有 $32$ 条不同的合法检验路径。
数据范围
对于 $30\%$ 的测评数据，满足 $1 \le N \le 100$ ， $1 \le M \le 1000$ 。
对于 $80\%$ 的测评数据，满足 $1 \le N \le 100$ ， $1 \le M \le 5000$ 。
对于 $100\%$ 的测评数据，满足 $1 \le N \le 1000$ ， $1 \le M \le 10000$ ， $1 \le U_i,V_i \le N$ ， $U_i \neq V_i$ 。
测试数据保证答案不超过 $3 \times 10^7$ 。
---
**题目来源：** 24年7月-C组（大咖）