체험 수업 도장 확인

문제

한 학원은 새로 등록한 학생들을 위해 여러 종류의 체험 수업을 운영한다. 등록 학생은 N명이며 학생 번호는 1번부터 N번까지다. 체험 수업의 종류는 K개이고, 수업 번호는 1번부터 K번까지다. 같은 종류의 수업이 여러 시간대에 열릴 수 있지만, 수료 여부를 판단할 때는 시간대와 관계없이 수업 종류만 구분한다. 학생이 수업을 마치면 출입 단말기에 학생 번호와 수업 번호를 남긴다. 단말기에 저장된 기록 한 줄은 해당 학생이 해당 종류의 수업을 적어도 한 번 마쳤다는 뜻이다. 기록은 실제 수업을 마친 순서와 다르게 모일 수 있으며, 학생 번호나 수업 번호 순서로 정렬되어 있지도 않다. 일부 단말기는 확인 버튼을 여러 번 누르면 같은 기록을 반복해서 저장한다. 또한 학생이 같은 종류의 수업을 다른 시간대에 다시 들을 수도 있다. 따라서 학생 번호와 수업 번호가 모두 같은 기록이 여러 번 나타날 수 있다. 이 기록들은 수료 여부를 판단할 때 하나의 도장으로만 인정한다. 다른 종류의 수업 기록을 대신하는 데 사용할 수는 없다. 학원은 K개 종류의 수업을 모두 한 번 이상 마친 학생에게 수료 배지를 준다. 한 학생에게 기록이 K줄 이상 있다고 해서 반드시 배지를 받는 것은 아니다. 서로 다른 수업 번호가 모두 나타나야 한다. 기록이 전혀 없는 학생도 등록 학생에 포함되지만, K는 양수이므로 그러한 학생은 배지를 받지 못한다. 주어진 기록만을 근거로 배지를 받을 학생의 전체 인원을 구한다. 또한 배지를 받을 학생 중 번호가 가장 작은 학생 한 명을 대표로 선택한다. 같은 학생에게 배지를 여러 개 주지 않으며, 수업을 마친 시각이나 기록의 입력 순서는 대표 선정에 영향을 주지 않는다. 조건을 만족하는 학생이 아무도 없으면 인원은 0으로, 대표 학생 번호는 -1로 표시한다.

입력

첫째 줄에 정수 N, K, M이 공백으로 주어진다. 1 ≤ N ≤ 100,000, 1 ≤ K ≤ 100,000, 0 ≤ M ≤ 25,000이다.
다음 M개 줄에는 학생 번호 a와 수업 번호 b가 공백으로 주어진다. a와 b는 정수이며 1 ≤ a ≤ N, 1 ≤ b ≤ K이다. 같은 a, b 쌍이 여러 번 주어질 수 있다.

출력

배지를 받을 학생 수와 그중 번호가 가장 작은 학생 번호를 한 줄에 공백으로 구분하여 출력한다. 배지를 받을 학생이 없으면 0 -1을 출력한다.

5 3 11
1 1
1 2
1 3
2 1
2 1
2 3
4 3
4 2
4 1
4 1
5 2

2 1

4 2 5
2 1
2 1
3 2
3 2
4 1

0 -1

3 1 4
3 1
3 1
2 1
2 1

2 2

출처: Devin.KR 자체 제작