#2378. 仙人掌
仙人掌
仙人掌
题目描述
1 仙人掌 1.1 题目描述 如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人 掌。所谓简单环即不经过重复的结点的环。 现在九条可怜手上有一张无自环无重边的无向连通图,但是她觉得这张图中的边数太少了, 所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图,图中的边数又不能太多。 经过权衡,她想要加边后得到的图为一棵仙人掌。 不难发现合法的加边方案有很多,可怜想要知道总共有多少不同的加边方案。 两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。 1.2 输入格式 多组数据,第一行输入一个整数T 表示数据组数。 每组数据第一行输入两个整数n, m,表示图中的点数与边数。 接下来m 行,每行两个整数u, v(1 ≤u, v ≤n, u̸ = v) 表示图中的一条边。保证输入的图 联通且没有自环与重边。 1.3 输出格式 对于每组数据,输出一个整数表示方案数,当然方案数可能很大,请对998244353 取模后 输出。 1.4 样例输入 2 3 2 1 2 2
1 3 5 4 1 2 2 3 2 4 1 5 1.5 样例输出 2 8 1.6 样例䀓䟺 对于第一组样例合法加边的方案有{}, {(2, 3)},共2 种。 1.7 数据范围与约定 测试点编号 ∑n m 其他约定 1 ≤5 ≤10 无 2 ≤2000 ≤2 × 105 3 4 ≤105 = n −1 图为一条链 5 6 无 7 8 ≤5 × 105 ≤106 9 10 对于100% 的数据,保证1 ≤m ≤n(n−1) 2 , ∑m ≤106。 ⌘意T 可能Պ较大,请⌘意᧗制初始化的复ᵲ度。 选手目录下的大数据中,四组数据依次满足第2, 4, 6, 8 个点的条件。 3
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
3 2
1 2
1 3
5 4
1 2
2 3
2 4
1 5
2
8