Codeforces Beta Round 23 |
---|
Закончено |
В 2N - 1 ящике лежат яблоки и апельсины. Требуется выбрать N ящиков так, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов.
В первой строке входного файла содержится одно число T — количество тестов. Описание каждого теста начинается с натурального числа N — количества ящиков. Далее в каждой из следующих 2N - 1 строке записаны числа ai и oi — количество яблок и апельсинов в i-ом ящике (0 ≤ ai, oi ≤ 109). Сумма N по всем тестам во входных данных не превышает 105. Все числа во входных данных целые.
Для каждого теста выведите две строки. В первой строке выведите YES, если возможно выбрать N ящиков, или NO — в противном случае. В случае положительного ответа во второй строке выведите N чисел — номера выбранных ящиков. Ящики нумеруются с 1 в том порядке, в котором они заданы во входных данных. Иначе оставьте вторую строку пустой. Разделяйте числа одним пробелом.
2
2
10 15
5 7
20 18
1
0 0
YES
1 3
YES
1
Название |
---|