버스 구간 기록 검사

문제

버스 노선 데이터를 정리하는 담당자는 승차 정류장 번호와 하차 정류장 번호가 적힌 구간 기록을 전달받았다. 이번에 검사할 노선은 한 방향으로만 운행하며, 정류장에는 운행 순서대로 1부터 S까지의 번호가 붙어 있다. 버스는 번호가 작은 정류장에서 큰 정류장으로 이동한다. 각 기록에는 한 승객이 탔다고 입력된 정류장 번호 A와 내렸다고 입력된 정류장 번호 B가 들어 있다. 자료를 입력하는 과정에서 존재하지 않는 정류장 번호가 적히거나 승차와 하차 순서가 잘못 적힐 수 있다. 담당자는 두 번호가 모두 실제 정류장 번호이고, 승차 정류장이 하차 정류장보다 앞에 있을 때만 그 기록을 정상으로 분류한다. 따라서 정상 기록은 1≤A<B≤S를 만족해야 한다. 같은 정류장에서 타고 내린 것으로 적힌 기록은 정상으로 보지 않는다. 번호가 노선 범위를 벗어난 기록도 정상으로 보지 않는다. 검사에서 정상으로 분류되지 않은 기록은 모두 제외한다. 번호를 서로 바꾸거나 범위 안으로 고치는 작업은 하지 않는다. 각 기록은 다른 기록과 관계없이 독립적으로 검사한다. 같은 두 번호가 여러 번 나와도 서로 다른 기록이므로 각각 정상 기록 수 또는 제외 기록 수에 더한다. 기록이 실제 운행 순서대로 주어지는지는 검사에 영향을 주지 않는다. 전체 자료를 검사한 뒤 정상 기록 수와 제외 기록 수를 구한다. 두 수의 합은 입력된 기록 수와 같아야 한다. 노선에 정류장이 하나뿐이면 정상인 구간은 존재하지 않는다. 기록이 하나도 주어지지 않으면 두 수를 모두 0으로 출력한다. 이 작업에서는 이동 거리나 승객 수를 추가로 계산하지 않는다.

입력

첫째 줄에 정류장 수 S와 기록 수 N이 공백으로 구분되어 주어진다. S와 N은 정수이며 1≤S≤1,000, 0≤N≤1,000이다.
다음 N개 줄에 승차 정류장 번호 A와 하차 정류장 번호 B가 공백으로 구분되어 주어진다. A와 B는 정수이며 -1,000≤A,B≤2,000이다.

출력

정상 기록 수와 제외 기록 수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다.

5 6
1 5
2 4
3 3
5 2
0 3
2 6

2 4

1 3
1 1
0 1
1 2

0 3

8 0

0 0

출처: Devin.KR 자체 제작