메인 퀘스트
대작 RPG 게임 '고올드'에는 플레이어가 클리어해야 할 N개의 메인 퀘스트가 있습니다. 각 퀘스트는 1번부터 N번까지 번호가 매겨져 있습니다.
스토리의 매끄러운 진행을 위해 특정 퀘스트는 반드시 다른 퀘스트보다 먼저 클리어해야 한다는 '선행 관계'가 M개 존재합니다.
예를 들어 "A번 퀘스트는 B번 퀘스트의 선행 퀘스트이다"라는 정보가 있다면, 반드시 A를 먼저 클리어한 후에만 B 퀘스트를 시작할 수 있습니다.
효율적인 게임 클리어를 위해 민우는 다음과 같은 세 가지 대원칙을 세워 퀘스트를 수행하려고 합니다.
- 게임을 완전히 졸업하기 위해 주어진 N개의 퀘스트를 모두 클리어해야 합니다.
- 선행 관계가 있는 퀘스트들은 반드시 선행 조건을 지켜서 순서대로 클리어해야 합니다.
- 선행 조건을 만족하여 당장 시작할 수 있는 퀘스트가 여러 개라면, 그중 '퀘스트 번호가 가장 작은 것'부터 먼저 클리어합니다.
N개의 퀘스트와 M개의 선행 관계 정보가 주어졌을 때, 민우가 세운 원칙에 따라 모든 퀘스트를 클리어하는 최적의 순서를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 퀘스트의 개수 N과 선행 관계의 개수 M이 공백을 사이에 두고 주어진다.
둘째 줄부터 M개의 줄에 걸쳐 선행 관계를 나타내는 두 정수 A와 B가 공백을 사이에 두고 주어진다.
이는 A번 퀘스트를 B번 퀘스트보다 반드시 먼저 클리어해야 함을 의미한다.
출력
첫째 줄에 원칙에 따라 퀘스트를 수행하는 최적의 순서를 1번부터 N번까지 공백으로 구분하여 차례대로 출력한다.
만약 선행 관계에 모순이 발생하여 모든 퀘스트를 클리어하는 것이 불가능한 경우에는 -1을 출력한다.
제한 사항
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 300,000
- 1 ≤ A, B ≤ N (A ≠ B)
- 입력으로 주어지는 선행 관계는 중복되어 주어질 수 있습니다.
예제 입력 1
4 2
4 2
3 1예제 출력 1
3 1 4 2예제 입력 2
3 3
1 2
2 3
3 1예제 출력 2
-1
코멘트
topological sort
gg