#1928. 大鱼洽水

    ID: 1928 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2294来源:qoj.ac数据:公开样例最短路

大鱼洽水

大鱼洽水

题目描述

标题: 大鱼洽水 - Problem - QOJ.ac

#13452. 大鱼洽水

Statistics

The problem was used in the following contests:

出题人是懒的,数据是随的,题目是简单的,做法是显然的。凡是做题,随便搞搞就过了。


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

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

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

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

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

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

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

当然,根据惯例,我们要对这个期望对 998244353 取模。可以证明,答案一定可以表示为有理数 ab,你只要输出 a×b−1(mod998244353) 即可。

输入格式

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

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

下面 m 行,每行两个正整数 ui,vi,表示一条水道。

输出格式

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

样例数据

样例 1 输入

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

样例 1 输出

0
13
15
15
15
15

样例 2 输入

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

样例 2 输出

7
499122181
0
499122184
499122186
499122186

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

样例 3 输出

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

子任务

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

对于所有数据,都有 2≤n≤105,1≤m≤1.5×105,1≤C≤n。

对于 5% 的部分分,有 n≤300。

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6 7 1
1
1 2
2 3
2 4
3 4
2 5
2 6
5 6
0
13
15
15
15
15

样例 2

6 7 1
3
6 4
4 5
5 6
4 1
1 2
2 3
3 4
7
499122181
0
499122184
499122186
499122186