#P18662. LaLa and Monster Hunting (Part 2)
LaLa and Monster Hunting (Part 2)
LaLa and Monster Hunting (Part 2)
题目描述
魔法都市 Sharia 附近的森林中出现了一只可怕的怪物,一群勇敢的冒险者准备在几天后、怪物伤人之前猎杀它。然而 LaLa 知道,他们愿意冒险的真正原因是怪物体内会产生一种稀有的魔法石。LaLa 觉得它非常漂亮,希望在冒险者之前得到它。
LaLa 已经知道怪物的大致位置,但怪物很擅长伪装,躲在树枝构成的网络中时很难辨认。
为便于描述,将怪物建模为下图所示的一个六顶点图 。

这个图由一个三角形和一条从三角形某个顶点引出的、长度为三条边的路径组成。路径上的另外三个顶点与三角形的三个顶点互不相同。换言之,可以给其六个顶点编号为 ,其边集为 。
树枝网络建模为无向简单图 。一个候选是 的一个与 同构的子图。具体地,可以先从 删除一些边,再删除一些不与任何剩余边关联的顶点,使所得图的顶点重新编号后恰好成为 。LaLa 需要检查所有不同的候选,才能找到怪物。
请计算候选的数量,对 取模。
注意:统计的是子图,不要求是诱导子图。所选六个顶点在原图中可以存在额外边;删除的边不同可能得到不同的候选。只把同一个子图的顶点重新编号,不会产生新的候选。网络不一定连通。
输入格式
输入一组数据。
第一行包含两个整数 ,分别表示 的顶点数和边数。顶点编号为 。
接下来 行,每行包含两个整数 ,表示第 条无向边连接这两个顶点。
数据范围
- 所有输入均为整数。
- 。
- 。
- 对每条边,。
- 任意两条输入边不同,即不存在重边;也不存在自环。
输出格式
输出一个整数,表示与 同构的子图数量对 取模的结果。
样例输入 1
6 7
0 1
1 2
0 2
2 3
3 4
4 5
3 5
样例输出 1
4
样例输入 2
6 15
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出 2
360
样例说明
下面四张原题插图分别展示第一组样例的四个候选。实线是保留的边,虚线是删除的边。



