print2072. Эльфийская пирамидка

printЭльфийская пирамидка

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Когда гном Гимли был маленьким и гостил у эльфов в Лориэне, ему подарили мифриловую пирамидку, состоящую из стержня и нанизанных на него колец. Однако, перед входом в родные Железные Холмы, он столкнулся с проблемой: пирамидка оказалась слишком высокой и не пролезала во входные врата. Сопровождающий их эльф посоветовал ему снять верхнее кольцо и попробовать пройти. Гимли, как настоящий гном, послушал эльфа и решил сделать наоборот – снять самое нижнее кольцо.
Однако оказалось, что это не так просто: Гимли может снять кольцо только тогда, когда внутренний радиус всех колец выше него больше, чем внешний радиус снимаемого, или внешний радиус меньше, чем внутренний всех колец выше него. Если же какое-то кольцо мешает, то сначала необходимо снять его. Поэтому Гимли попросил вас узнать, сколько всего колец ему придется снять, прежде чем получится снять самое нижнее.
Важно, что кольца на пирамидке могут двигаться только вверх.
В первой строке входного файла находится одно целое число `n` `(1\ ≤\ n\ ≤\ 10^5)` – количество колец на пирамидке. В следующих `n` строках записано по два целых числа `s_i` и `w_i` `(1\ ≤\ s_i,\ w_i\ ≤\ 10^5,\ s_i\ <\ w_i)` – внутренний и внешний радиусы `i`-го кольца пирамидки. Самое верхнее кольцо имеет номер один.
В первой строке выходного файла выведите одно число – минимальное количество колец, которые необходимо снять, прежде чем можно будет снять нижнее кольцо. В следующей строке выведите номера этих колец в произвольном порядке.

Пример ввода

4
10 20
3 5
2 4
1 3

Пример вывода

2
2 3
Источник: neerc.ifmo.ru/school
loading