#P18662. LaLa and Monster Hunting (Part 2)

    ID: 17998 传统题 6000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-三元环计数四元环计数按度数定向补集计数贡献法稀疏状态重置

LaLa and Monster Hunting (Part 2)

LaLa and Monster Hunting (Part 2)

题目描述

魔法都市 Sharia 附近的森林中出现了一只可怕的怪物,一群勇敢的冒险者准备在几天后、怪物伤人之前猎杀它。然而 LaLa 知道,他们愿意冒险的真正原因是怪物体内会产生一种稀有的魔法石。LaLa 觉得它非常漂亮,希望在冒险者之前得到它。

LaLa 已经知道怪物的大致位置,但怪物很擅长伪装,躲在树枝构成的网络中时很难辨认。

为便于描述,将怪物建模为下图所示的一个六顶点图 GG。

原题中的六顶点怪物图G

这个图由一个三角形和一条从三角形某个顶点引出的、长度为三条边的路径组成。路径上的另外三个顶点与三角形的三个顶点互不相同。换言之,可以给其六个顶点编号为 a,b,c,x,y,za,b,c,x,y,z,其边集为 {ab,bc,ca,ax,xy,yz}\{ab,bc,ca,ax,xy,yz\}。

树枝网络建模为无向简单图 HH。一个候选是 HH 的一个与 GG 同构的子图。具体地,可以先从 HH 删除一些边,再删除一些不与任何剩余边关联的顶点,使所得图的顶点重新编号后恰好成为 GG。LaLa 需要检查所有不同的候选,才能找到怪物。

请计算候选的数量,对 998244353998244353 取模。

注意:统计的是子图,不要求是诱导子图。所选六个顶点在原图中可以存在额外边;删除的边不同可能得到不同的候选。只把同一个子图的顶点重新编号,不会产生新的候选。网络不一定连通。

输入格式

输入一组数据。

第一行包含两个整数 N,MN,M,分别表示 HH 的顶点数和边数。顶点编号为 0,1,…,N−10,1,\ldots,N-1。

接下来 MM 行,每行包含两个整数 ui,viu_i,v_i,表示第 ii 条无向边连接这两个顶点。

数据范围

  • 所有输入均为整数。
  • 2≤N≤1000002\le N\le100000。
  • 0≤M≤1000000\le M\le100000。
  • 对每条边,0≤ui<vi<N0\le u_i<v_i<N。
  • 任意两条输入边不同,即不存在重边;也不存在自环。

输出格式

输出一个整数,表示与 GG 同构的子图数量对 998244353998244353 取模的结果。

样例输入 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

样例说明

下面四张原题插图分别展示第一组样例的四个候选。实线是保留的边,虚线是删除的边。

第一组样例的候选1,原PDF插图

第一组样例的候选2,原PDF插图

第一组样例的候选3,原PDF插图

第一组样例的候选4,原PDF插图