버스

트리데뱌타야 공화국의 새 대통령은 취임하자마자 국가 대중교통 체계를 전면 개편했다. 인구 대상 사회학 조사 결과를 바탕으로 도시간 버스의 이상적인 일일 운행 시간표를 작성했고, 이는 공화국 의회의 승인을 받았다.

게다가 모든 버스를 동일한 신형 차량으로 교체하기로 했다. 매우 비싸지만 훨씬 안정적이고 아름답고 편안한 차량이다.

국가의 버스 네트워크는 1부터 N까지의 정수로 번호가 매겨진 N개의 도시를 포함한다.

이상적인 시간표에는 M개의 일일 운행이 있다. i번째 운행은 도시 Fi에서 시각 Xi에 시작하여 다른 도시 Gi에서 시각 Yi에 끝난다. 각 운행의 소요 시간은 0이 아니며 24시간보다 엄격히 작다. i번째 운행은 시각 Xi에 도시 Fi에 있는 버스 중 하나가 수행한다.

새 버스는 수리가 필요 없고 24시간 내내 운행할 수 있으므로, 어떤 시각에 어떤 도시에 도착한 버스는 언제나 같은 시각 또는 그 이후에 그 도시에서 출발하는 다른 어떤 운행도 수행할 준비가 되어 있다. 버스는 시간표에 있는 어떤 운행을 수행할 때만 도시에서 출발할 수 있다.

시간표는 무한히 오래 운영될 예정이므로, 유한한 수의 버스로는 이 시간표를 절대 감당하지 못할 수도 있다.

무한한 기간 동안 시간표대로 운행하는 데 충분한 새 버스의 최소 수를 구하라.

첫째 줄에 정수 N과 M이 주어진다(1 ≤ N, M ≤ 100 000). N은 도시의 수, M은 버스 운행의 수이다.

다음 M개 줄에는 각각 버스 운행의 설명이 주어진다. 출발 도시 번호 Fi, 출발 시각 Xi, 도착 도시 번호 Gi(Fi ≠ Gi), 도착 시각 Yi가 하나의 공백으로 구분되어 주어진다. 시각은 HH:MM 형식이며, HH는 00부터 23까지의 시, MM은 00부터 59까지의 분이다.

필요한 버스의 최소 수를 한 줄에 출력한다. 무한한 기간 동안 유한한 수의 버스로 시간표를 감당할 수 없다면 -1을 출력한다.