만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

즉흥 여행 (Easy)

면접 대비

시간 제한2초메모리 제한1024 MB

요약
방향 그래프에서 모든 나라가 다른 모든 나라에 도달할 수 있는지 판별합니다.
난이도

쉬움10점 중 3점

유형
그래프, BFS, DFS
정답자
아직 제출이 없습니다

문제

철민이는 종강을 기념하여 NN개의 나라로 즉흥 여행을 떠나기로 했다.

철민이가 조사한 바에 따르면 NN개의 나라 사이에는 총 MM개의 항공편이 있다. 각 항공편은 출발하는 나라와 도착하는 나라가 정해져 있다.

즉흥 여행이라서 철민이는 여행 계획을 미리 짜지 않았다. 대신 다음 방식으로 여행하기로만 정했다.

  • 먼저 여행을 시작할 나라를 정하고, 그 나라로 간다.
  • 그 다음부터는 현재 있는 나라에서 출발하는 항공편 중 원하는 것을 골라 탄다.
  • 같은 나라를 여러 번 방문할 수 있고, 같은 항공편을 여러 번 이용할 수도 있다.

이 계획을 본 당신은 철민이가 NN개의 나라를 모두 여행할 수 있을지 걱정되기 시작했다. 그래서 철민이가 어느 나라에서 출발하든 모든 나라를 여행할 수 있는지 미리 확인해 보기로 했다.

입력

첫째 줄에 나라의 개수 NN과 항공편의 개수 MM이 주어진다. (1≤N≤200 0001 \le N \le 200\,000, 0≤M≤500 0000 \le M \le 500\,000)

둘째 줄부터 MM개의 줄에 걸쳐 항공편 정보가 두 정수 vv, ww로 주어진다. 이는 vv번 나라에서 출발해 ww번 나라로 가는 항공편을 뜻한다. (1≤v,w≤N1 \le v, w \le N, v≠wv \ne w)

출력

시작점을 어떻게 고르더라도 모든 나라를 방문할 수 있는 경로가 있으면 Yes를, 없으면 No를 출력한다.

예제3

  1. 예제 1

    입력
    4 5
    1 2
    2 3
    3 1
    1 4
    4 1
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    4 4
    1 2
    2 3
    3 4
    4 2
    
    예상 출력
    No
    
  3. 예제 3

    입력
    4 4
    1 2
    2 1
    3 4
    4 3
    
    예상 출력
    No