UOJ Logo

NOI.AC

3S 512MB

#147. graph

统计

图(graph)

【题目描述】

HZY有一张无向连通图,她会随机挑一点作为起点,当她在一个点时,她会随机找一个还未访问过且从当前点能到达的点并走向它,若当前点所有出边所向的点均已访问过,她就会返回上一个点。HZY想要知道这样能走出的所有的n个点的访问顺序有几种。

一句话题面:求一张图的dfs序数目。

【输入格式】

第一行两个正整数 n, m,分别表示点数和边数。

接下来 m 行,每行两个数 ai, bi,表示这张图中存在 (ai, bi) 这条无向边,保证没有重边。

【输出格式】

输出一个数,表示不同顺序的个数,为了方便,只用输出模 998244353 意义下的值。

【样例输入1】

3 2
1 2
2 3

【样例输出1】

4

【样例解释】

{1, 2, 3}, {2, 1, 3}, {2, 3, 1}, {3, 2, 1}

【样例输入2】

5 7
1 2
3 1
4 2
5 2
3 5
3 2
1 5

【样例输出2】

48

【数据范围】

对于 20 % 的数据,n ≤ 10。

对于 40 % 的数据,n ≤ 12。

对于 60 % 的数据,n ≤ 14。

对于 80 % 的数据,n ≤ 16。

对于 100 % 的数据,n ≤ 18 ,m ≤ n(n−1)/2。