AVT VSU - Problem 1942. Guests

1942. Guests

Time Limit:	1 seconds
Memory Limit:	262144KB
Points:	100

Однажды Пончик узнал рецепт нового торта и пригласил в гости всех своих друзей. За день к Пончику пришло N гостей. Знайка записал время прихода и ухода каждого гостя и задался вопросом: а найдутся ли такие три гостя, что никто из них не встречался друг с другом (то есть не встречались ни первый со вторым, ни второй с третьим, ни первый с третьим). Помогите Знайке найти ответ на этот вопрос.

Пояснение: два гостя не встречались, если один из них ушёл раньше, чем пришёл другой.

Входные данные

В первой строке входных данных записано натуральное число N. В каждой из следующих N строк записано время прихода и ухода очередного гостя в формате 'ЧЧ:ММ:СС ЧЧ:ММ:СС' (смотрите примеры).

Выходные данные

Если найдутся такие три гостя, которые попарно не встречались друг с другом, то выведите три натуральных числа – их номера (гости нумеруются с единицы в порядке, в каком они даны во входных данных). В случае нескольких верных ответов выведите любой.

Если ни одной подходящей тройки гостей не существует, то выведите одно число -1.

Система оценки

Подзадача 1 (до 60 баллов): 3 ≤ N ≤ 500

Подзадача 2 (до 40 баллов): 500 < N ≤ 100000

Примеры

Входные данные

4
10:00:00 11:00:00
10:30:00 11:30:00
12:00:00 13:30:00
11:15:00 11:30:00

Выходные данные

1 3 4

Входные данные

3
14:00:00 15:00:00
09:00:00 12:00:00
12:00:00 13:00:00

Выходные данные

-1

Примечание

Во втором примере гость с номером 3 пришёл ровно в тот момент, когда ушёл гость с номером 2 – в этом случае считаем, что они встретились.

Remote Training on Programming

1942. Guests