配点:200 点
問題文
次の条件を満たす,N 頂点 K 辺の単純無向グラフを考えます:
- 頂点 1 と頂点 i とを結ぶ最短パスの長さが di である.(1≤i≤N)
このようなグラフを構築することは可能ですか?
判定してください.
制約
- 1≤Φ≤105
- 1≤N
- ∑ϕΦϕ(N)≤105
- 1≤K≤1012
- 0=d1<di<N(1<i≤N)
- 入力はすべて整数
入力
各テストケースの入力は,それぞれ以下の形式で与えられる:
出力
条件を満たすようなグラフが存在するならば Yes
,そうでなければ No
と出力せよ.
サンプル
たとえば,頂点対 (1,3),(2,5),(3,4),(3,5),(4,5) をそれぞれ結ぶ 5 本の辺を張ることで条件が満たされます.
入力例2
3
6 5
0 2 1 1 2 2
4 4
0 3 2 2
5 6
0 1 2 2 2