문제 설명
서비스 N개를 새 클러스터로 옮깁니다. 서비스는 1부터 N까지 번호가 붙어 있고, 어떤 서비스는 다른 서비스가 먼저 떠 있어야 배포할 수 있습니다.
모든 의존 관계를 지키는 배포 순서를 구해 주세요. 가능한 순서가 여러 개면 매번 지금 배포할 수 있는 서비스 중 번호가 가장 작은 것을 먼저 배포합니다.
의존 관계가 순환해서 모두 배포할 수 없다면 -1을 출력합니다.
입력
첫 줄에 서비스 수 N (1 ≤ N ≤ 100,000)과 의존 관계 수 M (0 ≤ M ≤ 200,000)이 주어집니다.
다음 M줄에 A B가 주어집니다. 서비스 A가 서비스 B보다 먼저 배포돼야 한다는 뜻입니다. 같은 관계가 여러 번 나올 수 있습니다.
출력
배포 순서를 공백으로 구분해 한 줄에 출력합니다. 불가능하면 -1을 출력합니다.
제한 사항
- 시간 제한 1초 — C·C++·Go 기준이고, 다른 언어는 더 줍니다.
- 메모리 제한 256MB
- 제출하면 예시 2개와 숨은 테스트 4개로 채점합니다.
입출력 예
입력 #1
4 3 1 3 2 3 3 4
출력 #1
1 2 3 4
입력 #2
3 3 1 2 2 3 3 1
출력 #2
-1