The new President of Far Far Away began his work with a complete revision of the country's public transport system. As a result, on the basis of sociological surveys of the population, an ideal daily schedule of intercity buses was compiled, approved by the Parliament of the Republic.
Moreover, it was decided to replace the entire bus fleet with the same new, very expensive, but much more reliable, beautiful and comfortable cars.
The bus network of the country covers N cities, numbered with integers from 1 to N.
The ideal schedule contains M daily flights, the i-th flight starts in city Fi at time Xi and ends in some other city Gi at time Yi. The duration of each flight is non-zero and strictly less than 24 hours. Flight i is performed by one of the buses located at time Xi in the city Fi.
New buses do not require repairs and can operate around the clock, so a bus that arrives at some point in time in a certain city is always ready at the same time or later to go to service any other flight from this city. The bus can leave the city only on a scheduled flight.
It is assumed that the schedule will operate indefinitely, so it may not be possible to serve it with any finite number of buses.
Determine the smallest number of new buses sufficient to keep the schedule running for an unlimited period of time.
Input
The first line contains integers N and M (1 ≤ N, M ≤ 100 000) — number of cities and bus routes respectively.
Each of the following M lines contains a description of the bus route: departure city number Fi, departure time Xi, destination city number Gi (Fi ≠ Gi), arrival time Yi, separated from each other by one space. Arrival and departure times are specified in the HH:MM format, where HH — hours from 00 to 23, MM — minutes from 00 to 59.
Imprint
Print one number — the minimum required number of buses. If the schedule cannot be served for an unlimited period of time by a finite number of buses, print the number -1.
Examples
| # |
Input |
Output |
| 1 |
4 6
1 10:00 2 12:00
1 10:00 3 09:00
3 12:00 4 23:00
2 11:00 4 13:00
4 12:00 1 11:00
4 12:00 1 10:30 |
8 |