캠핑 구역 예약 점검

문제

한 캠핑장의 예약 서비스를 담당하는 백엔드 개발자는 저장된 예약 자료를 점검하고 있다. 캠핑장은 번호가 붙은 여러 구역으로 나뉘어 있으며, 하나의 구역에는 같은 시각에 하나의 예약만 배정할 수 있다. 서로 다른 구역의 예약은 시간이 겹쳐도 문제가 없다. 이번 점검에서는 이미 저장된 예약을 취소하거나 수정하지 않고, 시간 충돌이 있는 구역의 개수만 구한다. 각 예약에는 구역 번호, 이용 시작 시각, 이용 종료 시각이 들어 있다. 시각은 점검 기준 시점으로부터 지난 시간을 나타내는 정수이다. 시작 시각이 S이고 종료 시각이 E인 예약은 S 이상 E 미만인 시간 동안 구역을 사용한다. 따라서 어떤 예약이 끝나는 시각에 다른 예약이 바로 시작하는 경우에는 두 예약이 충돌하지 않는다. 모든 예약은 시작 시각보다 종료 시각이 늦다. 같은 구역에 배정된 서로 다른 두 예약이 함께 구역을 사용하는 시간이 조금이라도 있으면 그 구역에는 충돌이 있다고 판단한다. 시작 시각과 종료 시각이 모두 같은 예약이 두 번 저장되어 있어도 서로 다른 예약으로 취급하므로 충돌에 해당한다. 한 예약이 다른 예약의 이용 시간 전체를 포함하는 경우에도 충돌이다. 한 구역에서 충돌하는 예약 쌍이 여러 개 발견되더라도 그 구역은 한 번만 센다. 예약이 하나뿐인 구역과 예약이 없는 구역에는 충돌이 없다. 입력 자료는 구역 번호나 시작 시각에 따라 정렬되어 있지 않을 수 있다. 전체 예약을 조사하여 충돌이 있는 구역의 수를 구해야 한다. 충돌하는 예약 쌍의 수나 예약을 처리할 순서는 출력하지 않는다. 모든 구역에서 예약 시간이 서로 겹치지 않는다면 결과는 0이다.

입력

첫째 줄에 구역 수 C와 예약 수 N이 공백으로 주어진다. C는 1 이상 100 이하, N은 0 이상 20,000 이하의 정수이다.
다음 N개 줄에 예약 하나를 나타내는 구역 번호 P, 시작 시각 S, 종료 시각 E가 공백으로 주어진다. 모두 정수이며 1≤P≤C, 0≤S<E≤10,000이다.
같은 내용의 예약이 여러 번 주어질 수 있으며 각각 별개의 예약이다.

출력

시간 충돌이 있는 구역의 수를 정수 하나로 출력한다.

3 6
1 5 9
2 0 4
1 2 6
2 4 8
3 7 10
1 9 12

1

2 4
1 1 3
1 1 3
2 0 10
2 4 5

2

4 0

0

출처: Devin.KR 자체 제작