分数: 6 点
警告
2021 年 7 月 17 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
有 N 高桥王国的城市,称为City 1, 城市 2, \ldots, 城市 N.
还有 M 这个王国里有单行道路,你可以使用 i从城市出发的第 条路 u_i 前往城市 v_i.
(请注意,道路是单向的,即 i-th 路不允许您从 City 出发 v_i 前往城市 u_i.)
青木王国的居民青木来到高桥王国观光。在逗留期间,他将重复以下行程:
- 如果他从当前所在城市仅用一条路就可以到达一个或多个城市,他会选择其中一个可到达的城市并到达那里。
- 如果从当前所在城市仅用一条道路无法到达的城市,他将返回青木王国。
通过选择开始旅行的适当城市并在旅行期间不断做出适当的选择,确定 Aoki 是否可以无限期地继续旅行而不返回自己的国家。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- u_i \neq v_i
- i \neq j \Rightarrow (u_i, v_i) \neq (u_j, v_j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
如果 Aoki 可以无限期地继续旅行,则打印 Yes;否则,打印 No.
示例输入 1
3 3 1 2 2 1 2 3
示例输出 1
Yes
从城市出发 1 并继续以这种方式旅行 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow \cdots,他可以无限期地继续他的旅行。
示例输入 2
8 7 2 4 2 8 7 3 6 1 8 4 8 3 5 3
示例输出 2
No