문제 설명
성준이는 N명의 양궁 선수들의 순위를 예측하려고 합니다.
양궁 선수들 중 두 명이 겨룬 승패 기록이 주어졌을 때, 양궁 선수의 순위가 될 수 있는 범위를 구하세요.
그리고 우열을 가릴 수 없는 선수가 한 명이라도 존재한다면 순위를 예측할 수 없습니다.
예를 들어 A, B, C 선수가 있을 때, A선수가 B 선수를, B 선수가 C 선수를, C선수가 A선수를 이긴 경우 어느 선수가 우수한지 알 수 없으므로 순위를 예측할 수 없습니다.
입력 설명
첫째 줄에 N(1 <= N <= 256), M(1 <= M <= 100,000)이 주어집니다. N은 양궁 선수들의 수이며, M은 성준이가 확인한 경기 개수입니다. 다음 M개의 줄에는 경기에 참여한 선수의 번호 A, B가 주어지며, 이는 A번 선수가 B번 선수를 이겼다는 것을 의미합니다.
출력 설명
N개의 줄에 선수들의 예상되는 순위의 범위를 출력합니다. 순위를 예측할 수 없는 선수가 단 한 명이라도 존재하는 경우에는 첫째 줄에 -1 하나만 출력합니다.
도움
가능한 경우는 다음과 같습니다.
1 2 4 3
1 4 2 3
2 1 4 3
2 4 1 3
4 1 2 3
4 2 1 3
위 출력 예시와 같이 정답을 구할 수 있습니다.
만약 입력이 다음과 같이
4 3
1 2
2 1
3 4
와 같이 주어진 경우, 1번 선수와 2번 선수가 서로 이기거나 졌기 때문에 순위를 예측할 수 없습니다. 이 경우 출력은 다음과 같이,
-1
하나만 출력합니다.