グラフ彩色
v 個の頂点と e 本の辺を持つグラフに、c 種類の使用可能な色が与えられています。隣接する頂点が同じ色にならないように、与えられた c 種類の色でグラフを彩色できるかどうかを判定してください。入力
最初の行には、頂点の数を表す
v (1 ≤ v ≤ 20)、辺の数を表す e (0 ≤ e ≤ )、そして使用可能な色の数を示す c (1 ≤ c ≤ 10) の 3 つの整数が与えられます。続く
e 行にはグラフの辺が与えられます。各行には頂点 a と b (1 ≤ a, b ≤ n, a ≠ b) が書かれており、これは頂点 a と頂点 b の間に辺が存在することを示します。出力
もし、隣接する頂点が同じ色にならないように
c 種類の色でグラフを彩色できるなら YES を、そうでなければ NO を出力してください。例
入力 | 出力 |
3 3 3
1 2
2 3
3 1 | YES |
3 3 2
1 2
2 3
3 1 | NO |
4 4 2
1 2
2 3
3 4
4 1 | YES |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB