403226: GYM101081 I Polish Solidarity

Gdanks city became known worldwide in the early 80's by the work of the Solidarność (Solidarity) syndicate, led by Lech Wałȩsa,, who became president of Poland years later. At that time, Walesa dealt with the communism regime. He started a process that helped to finish the communism in Eastern Europe at the late 80's.

Wałȩsa was a leader that never got late. He was known for attending several syndicate's meetings and never leaving during a meeting. However, he demanded the starting and finishing times of each meeting, in order to prepare his agenda. Each committee published the stating and finishing time of its meeting. Walesa chose the meetings that he was going to attend each day in such a way that he would attend as many meetings as possible.

Your task is to make a program that receives a list of meetings and chooses a subset of meetings that doesn't overlap and with maximum size, following Wałȩsa's preferences.

The first line contains a number N of syndicate's meetings. The meetings are identified by integers from 1 to N in the order they are given in the input. The following N lines contain the starting and finishing times (in this order) of a meeting in the format HH : MM (exactly two digits for each). You can start a meeting the same minute you end another meeting. All the meetings start and finish in the same day. It is guaranteed the end time is after the start time.

Limits

• 1 ≤ N ≤ 10⁵
• 0 ≤ HH ≤ 23
• 0 ≤ MM ≤ 59

For each instance print the list of meetings chose by Wałȩsa. The meetings must be printed in the order of its starting time. If there are multiple possible answers, print any of them.

3
08:15 08:45
08:00 08:30
08:30 09:00

2 3 

5
11:00 12:00
12:20 13:15
10:10 12:15
12:30 13:00
10:30 12:16

1 4 

3
15:23 16:02
15:00 16:02
15:27 16:02

2