手铐
题号：NC14394
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给你一个连通无向图，保证每个点最多属于一个简单环，每个点度数最多为3，求这个图有多少“手铐图形个数”

其中“手铐图形个数”，定义为三元组(x,y,S)，其中x和y表示图上的两个点，S表示一条x到y的简单路径，而且必须满足：

1.x和y分别在两个不同的简单环上

2.x所在的简单环与路径S的所有交点仅有x，y所在的简单环与路径S的所有交点仅有y。

(x,y,S)与(y,x,S)算同一个手铐

如果你无法理解，可以参考样例。

输入描述:

第一行两个数n和m
之后m行，每行两个数x，y表示x和y之间有一条边。

输出描述:

输出一个数，表示手铐的个数对19260817取模的结果
示例1

输入

复制 
11 12
1 2
2 3
3 4
4 5
5 1
4 6
6 7
7 8
8 9
9 10
10 11
11 7

输出

复制 
1

说明

有(4,5,1,2,3)—6—(7,8,9,10,11)这一个手铐

示例2

输入

复制 
14 16
1 2
2 3
3 4
4 1
3 5
5 6
6 7
7 8
8 9
9 6
9 13
13 14
13 10
10 11
11 12
12 10

输出

复制 
4

说明


备注:

n <= 1000000
m <= 2000000