問題文

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

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

制約

• $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)$
• 与えられるグラフは連結
• 入力は全て整数

入力例 1Copy

3 3 3
1 2
2 3
1 3

出力例 1Copy

Yes

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

入力例 2Copy

4 3 3
1 2
2 3
2 4

出力例 2Copy

No