줄 서기
시간 제한2초메모리 제한128 MB
학생 N명과 선후 관계 제약 M개가 주어질 때 순환이 있으면 -1을 출력하고, 아니면 가능한 모든 배치에서 각 학생이 차지할 수 있는 최소, 최대 위치를 구합니다.
문제
N명의 학생이 키 순서대로 한 줄로 서려고 한다. 모든 학생의 키를 직접 재어 정렬할 수는 없어서, 일부 학생 쌍에 대해 누가 앞에 서야 하는지만 비교했다.
비교 결과가 주어졌을 때, 각 학생이 줄에서 설 수 있는 위치의 가장 앞쪽과 가장 뒤쪽을 구하시오. 위치는 앞에서부터 1번부터 N번까지이다.
입력
첫째 줄에 N(1 ≤ N ≤ 256)과 M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다.
다음 M개의 줄에는 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B보다 앞에 서야 한다는 뜻이다. 같은 두 학생을 여러 번 비교했을 수도 있다. A와 B가 같은 경우는 없다.
출력
N개의 줄을 출력한다. i번째 줄에는 i번 학생이 설 수 있는 가장 앞쪽 위치와 가장 뒤쪽 위치를 출력한다.
모든 비교 결과를 만족하는 줄을 만들 수 없다면 첫째 줄에 -1을 출력한다.
힌트
주어진 공개 테스트에서는 1번 학생과 2번 학생 사이의 순서는 정해지지 않았지만, 두 학생 모두 3번 학생보다 앞에 서야 한다. 따라서 1번과 2번 학생은 각각 1번부터 2번 위치까지 설 수 있고, 3번 학생은 3번 위치에만 설 수 있다.