E - Thin Ice 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

N 頂点 M 辺の連結無向グラフが与えられます。 i\ (1 \le i \le M) について、 i 番目の辺は頂点 A_i と頂点 B_i をつなぐ辺です。

全ての辺をちょうど K 回ずつ通るウォークが存在するか判定してください。

ウォークとは？ 長さ n の頂点列 v=(v_1 , v_2 \ldots v_n) のうち、任意の正整数 i\ (1 \le i \le n-1) について、v_i と v_{i+1} が直接辺で結ばれているようなものを指します。

制約

  • 2 \leq N \leq 2\times 10^5
  • N-1 \leq M \leq \min(\frac{N(N-1)}{2} , 2\times 10^5)
  • 1 \le K \le 10^9
  • 1 \le A_i < B_i \le N
  • 1 \le i < j \le M について、 (A_i,B_i) \neq (A_j,B_j)
  • 与えられるグラフは連結
  • 入力は全て整数

入力

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

N M K
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

条件を満たすウォークが存在する場合は Yesを、存在しない場合は No を出力せよ。

入力例 1

3 3 3
1 2
2 3
1 3

出力例 1

Yes

1 → 2 → 3 → 1 → 2 → 3 → 1 → 2 → 3 → 1 のウォークが条件を満たします。

入力例 2

4 3 3
1 2
2 3
2 4

出力例 2

No