경주 순위

자동차 경주에서 운전자들의 현재 순위를 계산하는 프로그램을 작성하라.

폐쇄된 경주로에는 1번부터 K번까지 번호가 붙은 K개의 체크포인트가 있다. 각 체크포인트에는 심판이 있으며, 어떤 운전자가 체크포인트를 지나면 심판은 컴퓨터 시스템에 운전자 번호와 체크포인트 번호를 보낸다. 운전자는 1번부터 N번까지 번호가 붙어 있다.

경주는 1번 체크포인트 바로 앞에서 시작하므로, 각 운전자가 처음으로 올바르게 지나야 하는 체크포인트는 1번이다. K번 체크포인트를 지난 뒤에는 다시 1번 체크포인트가 다음 올바른 체크포인트가 된다.

운전자는 체크포인트를 이 순서대로 지나야 한다. 어떤 메시지의 체크포인트가 그 운전자가 다음에 지나야 할 체크포인트가 아니라면, 그 메시지는 무시한다.

올바르게 지난 체크포인트 수가 많은 운전자가 더 높은 순위이다. 올바르게 지난 체크포인트 수가 같은 운전자들이 있다면, 마지막으로 올바르게 지난 체크포인트를 더 이른 시각에 지난 운전자가 더 높은 순위이다.

위 그림은 체크포인트가 5개인 경주로를 보여준다. 운전자는 체크포인트를 올바른 순서로 지나야 하며, 연속된 두 필수 체크포인트 사이에 있는 다른 체크포인트 통과는 무시된다.

첫째 줄에 세 정수 K, N, M이 주어진다.

• 1 <= K <= 100
• 1 <= N <= 100
• 1 <= M <= 10000

다음 M개의 줄에는 두 정수 X와 Y가 주어진다. 이는 X번 운전자가 Y번 체크포인트를 지났다는 뜻이다.

메시지는 시간 순서대로 주어진다.

주어지는 테스트 데이터에서는 순위가 항상 올바르게 결정된다.

M개의 메시지를 모두 처리한 뒤, 모든 운전자의 최종 순위를 한 줄에 출력한다.