E - Thin Ice
Editorial
/
Time Limit: 2 sec / Memory Limit: 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