D. Dirty Deeds Done Dirt Cheap
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано $$$n$$$ пар целых чисел $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$. Все элементы в парах различны и лежат в диапазоне от $$$1$$$ до $$$2 \cdot n$$$ включительно.

Назовём последовательность чисел $$$x_1, x_2, \ldots, x_{2k}$$$ хорошей, если выполняется одно из двух:

  • $$$x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$$$, или
  • $$$x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$$$.

Вам нужно выбрать какое-то подмножество различных индексов $$$i_1, i_2, \ldots, i_t$$$ и их порядок так, что если записать все числа из соответствующих пар в одну последовательность (эта последовательность будет $$$a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$$$), то эта последовательность будет хорошей.

Какое наибольшее по размеру подмножество пар можно выбрать? Вам также нужно построить соответствующую последовательность индексов $$$i_1, i_2, \ldots, i_t$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — количество пар.

В следующих $$$n$$$ строках вводятся два числа — $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot n$$$) — элементы очередной пары.

Гарантируется, что все числа в парах различны. Иначе говоря, каждое число от $$$1$$$ до $$$2 \cdot n$$$ упомянуто ровно один раз.

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

В первой строке выведите целое число $$$t$$$ — искомое число пар.

В следующей строке выведите $$$t$$$ различных целых чисел $$$i_1, i_2, \ldots, i_t$$$ — индексы пар в том порядке, в котором получается хорошая последовательность.

Примеры
Входные данные
5
1 7
6 4
2 10
9 8
3 5
Выходные данные
3
1 5 3
Входные данные
3
5 4
3 2
6 1
Выходные данные
3
3 2 1
Примечание

Итоговая последовательность в первом тесте из условия: $$$1 < 7 > 3 < 5 > 2 < 10$$$.

Итоговая последовательность во втором тесте из условия: $$$6 > 1 < 3 > 2 < 5 > 4$$$.