만드는 중입니다

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

변호사들

면접 대비

시간 제한1초메모리 제한512 MB

요약
N명의 변호사와 M개의 방향 신뢰 간선이 주어질 때, 모든 변호사가 최소 한 명에게 변호를 받고 서로 변호하는 쌍이 없는지 판별합니다.
난이도

보통10점 중 4점

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

문제

NN명의 변호사가 사기 범죄를 저지른 혐의로 기소되었다. NN명의 변호사는 서로를 변호하여 전원 무사히 무죄로 처리되려고 한다.

변호사들은 자신이 신뢰하는 변호사에게만 변호를 받을 수 있다. 이 신뢰관계는 MM개의 (A,B)(A, B) 쌍으로 표현된다. 이는 변호사 BB가 변호사 AA를 신뢰한다는 뜻이며, 이 경우에만 변호사 AA가 변호사 BB를 변호할 수 있다.

각 변호사의 실력은 매우 뛰어나기 때문에, 1명 이상의 변호를 받은 사람은 무조건 무죄가 된다. 단, 두 변호사 AA, BB에 대해 AA가 BB를 변호하고 BB가 AA를 변호하는 경우는 매우 수상하기 때문에 둘 모두 유죄가 된다.

각 (A,B)(A, B) 쌍에 대해 변호사 AA가 변호사 BB를 변호할지 말지를 선택하여 모든 변호사가 무죄가 되는 것이 가능한지 판정하라.

입력

첫 줄에 NN과 MM이 주어진다. (1≤N,M≤200,0001 \le N, M \le 200,000)

두 번째 줄부터 MM개의 줄에 걸쳐 ii번째 줄에는 서로 다른 두 정수 AiA_i, BiB_i가 주어진다. 이는 변호사 AiA_i가 변호사 BiB_i를 변호할 수 있다는 뜻이다.

같은 순서쌍 (A,B)(A, B)가 중복하여 나타나는 경우는 없다.

출력

모든 변호사가 1명 이상의 변호를 받고, 서로를 변호하는 변호사 쌍이 없도록 할 수 있는 경우 첫 줄에 YES를 출력한다.

불가능한 경우 첫 줄에 NO를 출력한다.

예제3

  1. 예제 1

    입력
    3 3
    1 2
    2 3
    3 1
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    4 6
    1 2
    1 3
    1 4
    2 3
    2 4
    3 4
    
    예상 출력
    NO
    
  3. 예제 3

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