← 返回题目列表

AtCoder · pakencamp_2023_day1_e

E. 薄冰

中文机器翻译题面 查看原题

配点 : 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