配点:200200

問題文

次の条件を満たす,NN 頂点 KK 辺の単純無向グラフを考えます:

  • 頂点 11 と頂点 ii とを結ぶ最短パスの長さが did_i である.(1iN)\scriptsize \; (1 \leq i \leq N)

このようなグラフを構築することは可能ですか? 判定してください.

制約

  • 1Φ1051 \leq \Phi \leq 10^5
  • 1N1 \leq N
  • ϕΦϕ(N)105\sum_{\phi} \Phi_{\phi}(N) \leq 10^5
  • 1K10121 \leq K \leq 10^{12}
  • 0=d1<di<N  (1<iN)0 = d_1 < d_i < N \; \scriptsize (1 < i \leq N)
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NKN \enspace K
d1d2dNd_1 \enspace d_2 \enspace \cdots \enspace d_N

出力

条件を満たすようなグラフが存在するならば Yes,そうでなければ No と出力せよ.

サンプル

入力例1
1
5 5
0 3 1 2 2
出力例1
Yes

たとえば,頂点対 (1,3),(2,5),(3,4),(3,5),(4,5)(1, 3), (2, 5), (3, 4), (3, 5), (4, 5) をそれぞれ結ぶ 55 本の辺を張ることで条件が満たされます.


入力例2
3
6 5
0 2 1 1 2 2
4 4
0 3 2 2
5 6
0 1 2 2 2
出力例2
Yes
No
Yes

Submit


Go (1.21)