만드는 중입니다

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

경찰서

면접 대비

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

요약
방향 그래프에서 모든 다른 정점에 도달할 수 있는 정점을 모두 찾아 오름차순으로 출력한다.
난이도

보통10점 중 4점

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

문제

은하에 초공간 고속도로망이 건설되었다. 각 고속도로는 두 행성을 잇는 일방통행 통로다. 은하 정부는 경찰서를 세울 행성을 고르려 한다.

경찰이 은하 전체를 지키려면 경찰서가 있는 행성에서 고속도로망을 따라 다른 모든 행성으로 갈 수 있어야 한다.

어떤 행성에서 경찰서로 고속도로를 타고 돌아올 수 있어야 하는 것은 아니다. 돌아오는 길에는 서두를 필요가 없어서 고속도로보다 느린 경로를 써도 된다.

일방통행 고속도로망이 주어진다. 고속도로를 몇 번 갈아타서 나머지 모든 행성에 도달할 수 있는 행성을 모두 구하여라.

입력

첫째 줄에 행성의 수 NN과 고속도로의 수 MM이 주어진다.

이어지는 MM개의 줄에 각각 두 정수 AiA_i와 BiB_i가 주어진다. ii번째 고속도로가 잇는 두 행성의 번호다. 이 고속도로는 일방통행이라서 행성 AiA_i에서 행성 BiB_i로 갈 때만 쓸 수 있다.

  • 1≤N,M≤1061 \leq N, M \leq 10^6
  • 모든 ii에 대해 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N이고 Ai≠BiA_i \neq B_i이다.
  • 같은 두 행성을 같은 방향으로 잇는 고속도로가 둘 이상 있지는 않다. 반대 방향으로 잇는 고속도로는 있을 수 있다.
  • 전체 테스트 데이터의 30%에서 N≤103N \leq 10^3이고 M≤3⋅103M \leq 3 \cdot 10^3이다.

출력

두 줄을 출력한다. 첫째 줄에는 경찰서를 세우기에 알맞은 행성의 개수를 출력한다. 둘째 줄에는 그 행성의 번호를 오름차순으로 공백 하나씩 띄워 출력한다. 알맞은 행성이 하나도 없으면 둘째 줄은 빈 줄로 출력한다.

예제2

  1. 예제 1

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

    입력
    3 2
    1 3
    2 3
    
    예상 출력
    0