Время на тест - 5 секунд.
На конференции работников народного образования с докладами об очередном улучшении финансирования желает выступить несколько министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.
Формат входных данных
Первая строка входных данных содержит целое число n, 0<n<=10000. Далее идет n строк, каждая из которых содержит два целых числа si и ti, 0<=si<ti<=30000. Каждая строка соответствует одной заявке с номером i (1<=i<=n), si является временем начала заявки, ti – временем ее окончания.
Программа должна найти подмножество множества {1, 2, ..., n}, содержащее наибольшее число элементов, такое, что для любых двух элементов i и j из найденного подмножества верно одно из двух неравенств: ti<=sj
или tj<=si. Указанные неравенства означают, что заявки с номерами i и j не пересекаются, то есть одна из них заканчивается не позднее, чем начинается другая. При этом время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки (один министр на трибуне меняется на другого министра).
Формат выходных данных
Программа должна вывести номера удовлетворенных заявок в произвольном порядке, разделяя их пробелами. Заявки нумеруются, начиная с 1.
Пример
Входные данные
3
1 3
2 4
3 5
Выходные данные
1 3
Входные данные
5
2 6
1 3
1 4
4 5
5 6
Выходные данные
2 4 5