가면 무도회

해마다 열리는 가면 무도회가 시작되었고, 동동이도 신나게 참가하려고 한다. 올해 가면은 주최자가 특별히 맞춘 것이다. 파티에 가는 사람은 각자 마음에 드는 가면을 하나 골라 쓰고 들어갈 수 있다. 가면에는 번호가 붙어 있고, 주최자는 가면을 쓴 사람에게 그 번호를 알려 준다.

파티 분위기를 더 신비롭게 만들기 위해 주최자는 가면을 k(k ≥ 3)가지 종류로 나누었고, 특수한 기술로 각 가면에 해당 종류의 표시도 해 두었다. 종류 i 가면을 쓴 사람만 종류 i + 1 가면을 쓴 사람의 번호를 볼 수 있다. 종류 k 가면을 쓴 사람은 종류 1 가면을 쓴 사람의 번호를 볼 수 있다.

파티에 온 손님들은 파티에 가면 종류가 몇 가지나 있는지 알지 못한다. 하지만 동동은 이것이 무척 궁금해져서 가면 종류가 몇 가지인지 직접 알아내기로 했다. 그래서 사람들 사이를 돌아다니며 정보를 모으기 시작한다.

동동이 모은 정보는 어떤 가면 번호를 쓴 사람이 어떤 가면 번호를 볼 수 있는지 알려 준다. 예를 들어 가면 번호 2를 쓴 사람은 가면 번호 5의 번호를 볼 수 있다는 식이다. 동동은 직접 몇몇 가면 번호를 보기도 하고, 그것으로 정보를 더 채우기도 한다.

모든 사람이 자기가 본 번호를 전부 기억하지는 못하므로, 동동이 모은 정보가 완벽하다고 보장할 수는 없다. 이제 동동이 현재 모은 정보를 바탕으로, 있을 수 있는 가면 종류 수의 최댓값과 최솟값을 구해야 한다. 주최자가 k ≥ 3이라고 이미 밝혔으니, 이 추가 정보도 고려해야 한다.

첫째 줄에 가면의 총 개수와 동동이 모은 정보의 총 개수를 나타내는 두 정수 n, m이 공백을 사이에 두고 주어진다.

다음 m개 줄에는 각각 두 정수 a, b가 공백을 사이에 두고 주어지며, 가면 a를 쓴 사람이 가면 b의 번호를 볼 수 있다는 뜻이다. 같은 a, b 쌍이 입력에 여러 번 나타날 수 있다.

n ≤ 100000, m ≤ 1000000.