← 返回题目列表

AtCoder · past202107_j

J. 永无止境的旅程

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

分数: 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