给你一个连通无向图，保证每个点最多属于一个简单环，每个点度数最多为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 m = 2000000
加载中...