경찰서

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

보통4그래프DFS구현면접 대비아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

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

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

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

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

입력

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

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

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

출력

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