根据贝尔兰总统发布的最后命令,该国每个城市都必须拥有自己的国防部大楼(自己的五角大楼)。大都市贝尔堡也不例外。该城市有 n 个交叉路口,其中一些对由双向道路连接。城市中总共有 m 条道路,每对路口之间不超过一条。
目前正在讨论为五角大楼在贝尔堡选址。已决定五角大楼应覆盖五个不同路口的领土,这些路口通过道路连接成一个自行车道。为了建造五角大楼,将在道路沿线建造一堵特殊的墙(具有高压剃须刀、高压线和其他属性)。因此,在城市中建造五角大楼的可能方式的数量等于长度为 5 的由交叉路口和道路组成的不同循环的数量。
你的任务是打印在贝尔堡建造五角大楼的方法数量。只有经过充分优化的解决方案才会被接受。请在最大测试用例上测试您的代码。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 700;0 ≤ m ≤ n·(n - 1) / 2),其中 n 表示路口的数量,m 是城市中道路的数量。然后遵循包含道路描述的 m 行,每行一个。每条道路由多个整数ai,bi(1≤ai,bi≤n;ai≠bi)设置,其中ai和bi代表由道路连接的路口的数量。结点从 1 到 n 编号。无法保证从任一路口可以到达沿道路行驶的任何其他路口。
输出
打印代表所需路数的单个数字。请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout (也可以使用 %I64d)。
示例
输入 #1
5 5 1 2 2 3 3 4 4 5 5 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
12