핵심 하위 프로젝트
시간 제한0.6초메모리 제한32 MB
DAG에서 다른 모든 정점과 도달 가능성으로 비교되는 정점을 모두 찾는다.
문제
큰 프로젝트 하나가 서로 다른 하위 프로젝트 개로 나뉘어 있다. 관리자는 하위 프로젝트 사이의 선후 관계를 정해 두었다. 하위 프로젝트 를 끝내야만 하위 프로젝트 를 시작할 수 있는 쌍 가 있고, 이때 가 에 직접 선행한다고 한다. 가 에 직접 선행하거나, 가 에 선행하고 가 에 선행하는 하위 프로젝트 가 있으면 가 에 선행한다고 한다.
를 제외한 모든 하위 프로젝트 에 대해 가 에 선행하거나 가 에 선행하면, 하위 프로젝트 를 핵심 하위 프로젝트라고 한다.
전체 프로젝트는 완료할 수 있다. 즉 자기 자신에게 선행하는 하위 프로젝트는 없다.
핵심 하위 프로젝트를 모두 찾는 프로그램을 작성하시오.
입력
첫째 줄에 정수 과 이 주어진다. ()은 하위 프로젝트의 개수이고, ()은 직접 선행 쌍의 개수다. 하위 프로젝트는 번부터 번까지의 번호로 구분한다. 이어지는 개 줄에는 각각 두 정수 와 ()가 주어지며, 이는 가 에 직접 선행한다는 뜻이다.
출력
첫째 줄에 핵심 하위 프로젝트의 개수를 출력한다. 둘째 줄에는 핵심 하위 프로젝트의 번호를 오름차순으로 출력하고, 번호 사이는 공백 하나로 구분한다. 핵심 하위 프로젝트가 하나도 없으면 첫째 줄에 만 출력하고 끝낸다.
힌트

첫 번째 예제의 선후 관계를 나타낸 그림이다.