G - mod998のやつを探してる人はまずこの問題を開けばいいと思います
Flavor
2
s
1024
MB
100
点
問題文
$2N$ 頂点 $M$ 辺の無向グラフ $G$ が与えられます。
$i = 1, 2, \ldots, M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結ぶ無向辺です。
$2N$ 個の頂点を $N$ 個のペアに分割する方法であって、下記の条件を満たすものの個数を $998244353$ で割った余りを出力してください。
各ペアをなす $G$ の $2$ 頂点間に無向辺を追加する。そうして得られる $2N$ 頂点 $(M+N)$ 辺の無向グラフにおいて、すべての $i = 1, 2, \ldots, 2N$ について、頂点 $1$ と頂点 $i$ の距離はちょうど $d_i$ である。
ここで、頂点 $u$ と頂点 $v$ の最短距離とは、頂点 $u$ と頂点 $v$ を結ぶパスの辺の本数の最小値です。
また、$2$ つの「 $2N$ 個の頂点を $N$ 個のペアに分割する方法」が異なるとは、一方の方法ではペアをなしているが他方の方法ではペアをなしていないような $G$ の $2$ つの頂点が存在することを言います。
制約
- $1 \leq N \leq 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \le u_i,v_i \le 2N$
- $0 \leq d_i \leq 2N$
- 入力はすべて整数
入力
入力は以下の形式で与えられる。
$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$d_1$ $d_2$ $\ldots$ $d_{2N}$
出力
答えを出力せよ。
入力例 1
3 6
1 2
1 3
3 4
4 5
5 6
6 3
0 1 1 2 2 1
出力例 1
3
下記の $3$ 通りの方法が、問題文中の条件を満たします。
- 頂点 $1$ と頂点 $6$ をペアにし、頂点 $2$ と頂点 $3$ をペアにし、頂点 $4$ と頂点 $5$ をペアにする。
- 頂点 $1$ と頂点 $6$ をペアにし、頂点 $2$ と頂点 $4$ をペアにし、頂点 $3$ と頂点 $5$ をペアにする。
- 頂点 $1$ と頂点 $6$ をペアにし、頂点 $2$ と頂点 $5$ をペアにし、頂点 $3$ と頂点 $4$ をペアにする。
入力例 2
2 4
1 2
1 2
2 2
3 4
0 1 1 2
出力例 2
1
与えられるグラフは、連結でない場合や、自己ループ・多重辺を持つ場合があります。
入力例 3
2 0
1 0 1 0
出力例 3
0
入力例 4
10 20
12 5
3 7
7 18
15 16
1 2
20 18
9 14
19 10
13 11
2 6
15 17
19 7
5 7
9 13
7 15
5 11
8 19
2 5
4 19
7 9
0 1 3 2 2 2 2 2 3 2 3 3 4 2 3 3 4 3 1 3
出力例 4
122850