Вам дано \(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\).
Выходные данные
В первой строке выведите целое число \(t\) — искомое число пар.
В следующей строке выведите \(t\) различных целых чисел \(i_1, i_2, \ldots, i_t\) — индексы пар в том порядке, в котором получается хорошая последовательность.
Примечание
Итоговая последовательность в первом тесте из условия: \(1 < 7 > 3 < 5 > 2 < 10\).
Итоговая последовательность во втором тесте из условия: \(6 > 1 < 3 > 2 < 5 > 4\).