你的朋友 Cajsa 有一个包含 $n$ 个顶点的图，她需要找到图中的最短环。为了做到这一点，她只是随机选取了一个顶点序列，幸运的是，这恰好是一个最短环。“概率是多少呢？”，她问自己，并编写了另一个程序来计算这个概率。

为了完成这项工作，Cajsa 需要一个算法来计算图中所有最短环的数量。她使用了一个自制的随机算法，其运行时间为 $O(1)$。但你怀疑这个算法是不正确的，因为显然它必须考虑图中的每一个顶点（对吧？）。你认为 Cajsa 的算法只是输出了一些随机数，而这些数字恰好在某些小图上是正确的。

为了回应这些质疑，Cajsa 生成了一堆图，并向你发起挑战，要求你验证她的答案是否正确。

给定一个包含 $n$ 个顶点和 $m$ 条边的无向图，你的任务是计算其中最短环的数量。

图中的环是指一条由不同顶点组成的路径，且路径的首尾顶点之间存在一条边。如果两个环包含的边集不同，则认为它们是不同的。因此，环 $3, 1, 2$ 和 $3, 2, 1$ 是同一个环，环 $1, 2, 3$ 和 $2, 3, 1$ 也被视为同一个环。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 3000, 3 \le m \le 6000$)，分别表示顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i \neq v_i \le n$)，表示在 $u_i$ 和 $v_i$ 之间有一条无向边。图中不会包含重边或自环。

保证图中至少包含一个环。注意，图不一定是连通的。

输出格式

输出一个整数，表示图中最短环的数量。

样例

样例输入 1

4 4
1 2
2 3
3 4
4 1

样例输出 1

1

样例输入 2

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

样例输出 2

10

样例输入 3

6 6
1 2
2 3
3 1
4 5
5 6
6 4

样例输出 3

2