#1910. Utopiosphere

    ID: 1910 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1963来源:qoj.ac数据:公开样例图论最小生成树

Utopiosphere

Utopiosphere

题目描述

标题: Utopiosphere - Problem - QOJ.ac

#10308. Utopiosphere

Statistics

The problem was used in the following contests:

称无重边,无自环的无向图为简单无向图。

给定一个 n 个点 m 条边的简单无向图 G。若我们给 G 的每条边指定一个整数值作为边权。满足每条边的边权都在 1 到 m 之间,且每条边的边权两两不同,则称这样的指定方法为 G 的一个赋值。

两个赋值 G0,G1 称为等价的,当且仅当对于 G 的每个子图 G′,其在两种赋值下的最小生成森林形状相同(即在忽略边权的情况下是同一个子图)。

给定一个 G 的赋值 G0,求与它等价的赋值的数量,答案对 998244353 取模。

一个带正权的无向图的最小生成森林,是指连通块数与原图相同的边权和最小的子图,可以证明,如果每条边的边权两两不同,那么这样的子图是唯一的。

输入格式

从标准输入读入数据。

第一行:两个整数 n,m。

接下来 m 行:每行三个整数 x,y,z,表示 G0 中 x,y 之间有一条边权为 z 的边。

保证每条边的边权都在 1 到 m 之间,且所有边权两两不同。

输出格式

输出到标准输出。

第一行:一个整数 ans,表示答案对 998244353 取模。

样例

输入

4 6
1 2 1
1 3 2
1 4 4
2 3 3
2 4 6
3 4 5

输出

8

解释

有如下八种赋值方式(边的顺序与输入一致):

  • [1,2,3,4,6,5]
  • [1,2,4,3,6,5]
  • [1,3,2,4,6,5]
  • [2,1,3,4,6,5]
  • [2,1,4,3,6,5]
  • [2,3,1,4,6,5]
  • [3,1,2,4,6,5]
  • [3,2,1,4,6,5]

子任务

对于全部数据:1≤n,m≤2×105。

Subtask 1 (10%):n≤12, m≤6。

Subtask 2 (15%):n,m≤200。

Subtask 3 (20%):n≤2000。

Subtask 4 (2%):G 是树。

Subtask 5 (13%):G 是仙人掌。

Subtask 6 (15%):G 是杏仁。

Subtask 7 (25%):无特殊限制。

下面是对上面一些图论术语的解释。

树:没有简单环的简单无向连通图。

仙人掌:任何一条边在至多一个简单环上的简单无向连通图。

杏仁:恰好有 n−2 个点的度数为 2 的简单无向连通图。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 6
1 2 1
1 3 2
1 4 4
2 3 3
2 4 6
3 4 5
8