A - 閉路グラフ Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

下図のような n(n3)n(n≧3) 頂点から成る閉路グラフがあります.

このグラフは,頂点 11 と頂点 22を結ぶ辺,頂点 22 と頂点 33,...,頂点 n1n-1 と頂点 nn,そして頂点 nn と頂点 11 を結ぶ辺から構成されています.

あなたは,このグラフからいくつかの頂点を取り除く(*)ことでグラフを分断し最終的に kk 個の連結成分のみが残ったグラフにしたいと思っています. 実際に頂点を取り除き始める前に,そのような取り除き方が本当に存在するかどうかを判定してください.

(*) ある頂点を取り除くと,その頂点に直接繋がっている辺も取り除かれます.また,必要がなければ 11 つも頂点を取り除かなくても構いません.


入力

入力は以下の形式で標準入力から与えられる.

nn
kk
  • 11 行目には,閉路グラフの頂点の数を表す整数 n(3n105)n (3 ≦ n ≦ 10^5) が与えられる.
  • 22 行目には,残したい連結成分の数を表す整数 k(1k105)k (1 ≦ k ≦ 10^5) が与えられる.

出力

1行目に,nn 頂点の閉路グラフからいくつかの頂点を取り除いて,ちょうど kk 個の連結成分を含むグラフにすることができるならば YES,そうでないならば NO を出力せよ.最後に改行を忘れないこと.


入力例1Copy

Copy
6
2

出力例1Copy

Copy
YES

例えば,下図のように,頂点 11 と頂点 33 を取り除くことで,ちょうど 22 つの連結成分を残すことができます.


入力例2Copy

Copy
3
2

出力例2Copy

Copy
NO

入力のグラフは下図の通りです.どのように頂点を取り除いても 22 つの連結成分のみを残すことは出来ません.


入力例3Copy

Copy
11
6

出力例3Copy

Copy
NO

入力例4Copy

Copy
11
5

出力例4Copy

Copy
YES


2025-03-14 (Fri)
01:05:41 +00:00