5080: 大鱼洽水

内存限制:512 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:4 通过:1

题目描述

你是大鱼,因为你和水很融洽,所以你在水里跑得贼快,于是你每天在水里跑来跑去。

直到有一天,你醒来发现你在一个由若干房间和水道组成的迷宫里。你轻松的得到了这个迷宫的地图:

你发现这个迷宫可以抽象成一个无向连通图没有重边自环,且每条边最多在一个简单环上。房间可以看做点,编号从$1$到$n$,水道可以看做边,直接连接着两个房间。

迷宫的路错综复杂,但是你一眼望穿了地图。虽然你知道怎么出去,但是你要完成你光荣的使命——卷,所以出去的事情另想办法。你发现你在卷的时候是难以看清路的,于是你选择了乱跑,也就是随机游走。

形式化地说,你会沿着当前房间连出的所有水道中等概率选择一条并且直接跑到这条水道的另一个端点(在跑的期间你要保持一直在这个水道上)。

你知道你一点都不卷,且你相信自己很欧,所以你把从迷宫出去的重担交给了 rp,把冲击的$151$题的小目标,留给了你自己。

不过,你并不知道你一开始在哪个房间。所以你想知道对于每个房间,如果你一开始在那里,从开始随机游走直到到达一个出口,期望经过多少条水道

当然,根据惯例,我们要对这个期望对$998244353$取模。可以证明,答案一定可以表示为有理数$\frac{a}{b}$,你只要输出$a\times b^{-1}(mod \ 998244353)$即可。

输入格式

第一行三个正整数$n,m,C$,分别表示房间的个数,水道的条数,出口的个数。

第二行$C$个正整数$c_i$,表示出口的编号,保证编号两两不相同且每个编号都代表着一个房间。

下面$m$行,每行两个正整数$u_i,v_i$,表示一条水道。

输出格式

共$n$行,每行一个范围在$[0,998244353)$的非负整数,表示在编号为$i$点出发,经过水道条数的期望。

输入样例 复制

#1
6 7 1
1
1 2
2 3
2 4
3 4
2 5
2 6
5 6

#2
6 7 1
3
6 4
4 5
5 6
4 1
1 2
2 3
3 4

#3
20 24 3
15 20 10
17 13
13 20
20 17
2 20
13 9
9 19
19 13
17 4
4 3
3 17
13 1
1 7
7 13
15 1
8 20
16 4
18 9
4 6
6 5
5 4
11 13
10 3
12 7
14 9

输出样例 复制

#1
0
13
15
15
15
15

#2
7
499122181
0
499122184
499122186
499122186

#3
873463818
1
873463818
499122191
499122193
499122193
499122189
1
790276796
0
124780557
499122190
124780556
790276797
0
499122192
124780554
790276797
457528677
0

数据范围与提示

由于某些原因,本题数据按类似对于每个点随机选一个编号比自己小的点连边的方法生成。这样的数据比较随机,很大程度上,可以忽略计算过程中,计算$0$的逆元的情况。

对于所有数据,都有$2\leq n \leq 10^5,1\le m \le 1.5\times 10^5,1\le C \le n$。

对于$5\%$的部分分,有$n\le 300$。

对于另外$5\%$的部分分,保证抽象出的图是一棵树。

对于另外$10\%$的部分分,保证抽象出的图的每个环上至少有一个出口。

对于另外$40\%$的部分分,保证$m=n$。