LCC/Moose '20 Contest 5 S1 - Herbs and Ghouls

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Chris really likes planting herbs in his herb garden. He has planted his garden as a single straight row of herbs. Unfortunately, every night a ghoul comes over and eats some of his herbs. Ghouls are very predictable, so they will start at a single herb and will eat some number of the next few herbs.

Over time, the ghoul comes and eats up Chris' herb garden. Chris wants to study the ghoul's herb eating behavior so he keeps track of exactly which range of herbs the ghoul eats every night.

Chris has decided that he wants to know which herbs the ghoul has not eaten yet. Can you help him?

Input Specification

The first line of input will contain a single integer, N (1 \leq N \leq 10^5) indicating that Chris has N herbs in his garden at the beginning.

The next line of input will contain a single integer, M (1 \leq M \leq 10^5) indicating that Chris has written down data for M nights of ghoul herb eating.

The next M lines will consist of 2 dash (-) separated integers, a and b, indicating that the ghoul has eaten all of the herbs between a and b (1 \leq a \leq b \leq N), inclusive.

Ghouls can only eat herbs that have not been eaten yet, so there will be no overlap in any of the ranges.

Output Specification

The output will consist of a list of ranges of herbs that the ghoul has not eaten yet, one per line.

A range should be formatted dash (-) separated, with the first integer being the start of the range and the second integer being the end of the range

Ranges are inclusive, so you can have the start and end of the range be the same integer.

Ranges should also be as long as they can be, for example 1-3 and 4-9 should be combined to 1-9.

Ranges do not need to be output in any particular order.


For 50\% of the marks, 1 \leq N, M \leq 100.

For the rest of the marks, there are no further constraints.

Sample Input


Sample Output


Explanation for Sample Input

Chris has 10 herbs in a row, the ghoul has eaten herbs 2, 3, 4, 5, 8, 9. This leaves the herbs 1, 6, 7, 10 left uneaten.


There are no comments at the moment.