J - 終わりなき旅 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

高橋王国には N 個の都市があり、それぞれ都市 1、都市 2、\ldots、都市 N と呼ばれています。
また、高橋王国には M 本の一方通行の道路があり、 i 番目の道路を通って都市 u_i から都市 v_i に移動することができます。
(道路は一方通行であるため、都市 v_i から都市 u_i には移動できないことに注意してください。）

高橋王国に観光旅行にやってきた青木王国の青木君は、N 個の都市のいずれかから出発し、 青木王国に帰るまでの間、以下の手順を繰り返して旅行をします。

  • 青木君が現在いる都市から道路をちょうど 1 本通って移動可能な都市が存在するならば、移動可能な都市の中から 1 つを選び、そこに移動する。
  • 青木君が現在いる都市から道路をちょうど 1 本通って移動可能な都市が存在しなければ、青木君は青木王国に帰る。

青木君が、出発する都市を適切に選択し、旅行中の移動先の都市を適切に選択しつづけることで、 青木王国に帰ることなくいくらでも旅行を続けることができるかどうか判定してください。

制約

  • 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

出力

青木君がいくらでも旅行を続けることができるなら 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

Score : 6 points

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N cities in the Kingdom of Takahashi, called City 1, City 2, \ldots, City N.
There are also M one-way roads in this kingdom, and you can use the i-th road to get from City u_i to City v_i.
(Note that the roads are one-way, that is, the i-th road does not allow you to get from City v_i to City u_i.)

Aoki, a resident of the Kingdom of Aoki, has come to the Kingdom of Takahashi for sightseeing. During his stay, he will travel by repeating the following:

  • If there are one or more cities that he can reach by using just one road from the city he is currently in, he will choose one of those reachable cities and get there.
  • If there is no city that he can reach by using just one road from the city he is currently in, he will go back to the Kingdom of Aoki.

Determine whether it is possible for Aoki to continue traveling indefinitely without returning to his country by choosing the appropriate city from which he starts his travel and keep making appropriate choices for where to go during his travel.

Constraints

  • 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)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If it is possible for Aoki to continue traveling indefinitely, print Yes; otherwise, print No.

Sample Input 1

3 3
1 2
2 1
2 3

Sample Output 1

Yes

By starting in City 1 and keep traveling in the manner 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow \cdots, he can continue his travel indefinitely.

Sample Input 2

8 7
2 4
2 8
7 3
6 1
8 4
8 3
5 3

Sample Output 2

No