줄 서기

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번 위치에만 설 수 있다.