Задача 8. Разбиение на пары

Автор:Центральная предметно-методическая комиссия   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Космические археологи обнаружили на планете в соседней звездной системе n древних артефактов, которые они пронумеровали от 1 до n. Каждый артефакт имеет k различных параметров, каждый параметр характеризуется целым числом. Артефакт i имеет параметры ai,1, ai,2, …, ai,k. Оказалось, что первые параметры у всех артефактов различны: для всех i ≠ j выполнено ai,1 ≠ aj,1, при этом другие параметры у артефактов могут совпадать.

Учёные также обнаружили текст, в соответствии с которым для активации артефактов их необходимо особым образом разбить на пары и совместить. Разбиение артефактов на пары является корректным, если для каждого t от 1 до k можно выбрать такое число bt, что оно лежит на отрезке между значениями t-го параметра артефактов каждой пары. То есть, если артефакты i и j образуют пару, должно выполняться условие ai,t ≤ bt ≤ aj,t или условие ai,t ≥ bt ≥ aj,t.

Теперь ученые хотят выяснить, верно ли расшифрован текст. Для этого необходимо проверить, существует ли корректное разбиение артефактов на пары. Каждый артефакт должен войти ровно в одну пару в разбиении.

Требуется написать программу, которая по описанию параметров артефактов определяет, можно ли разбить их на пары таким образом, чтобы для каждого параметра существовало значение, лежащее между значениями этого параметра артефактов каждой пары, и в случае положительного ответа выводит такое разбиение.

Формат входных данных

В первой строке заданы целые числа n и k — количество артефактов и количество параметров.

В следующих n строках задано по k целых чисел ai,1, ai,2, …, ai,k — параметры артефактов.

Формат выходных данных

Выведите NO, если требуемого разбиения на пары не существует.

В противном случае выведите YES в первой строке. Далее выведите n / 2 строк, в каждой строке выведите по два числа — номера артефактов, из которых следует составить пару. Каждый артефакт должен быть выведен ровно один раз.

Если существует несколько корректных разбиений артефактов на пары, разрешается вывести любое из них.

Ограничения

2 ≤ n ≤ 2⋅ 105, n чётно, 1 ≤ k ≤ 7

 − 109 ≤ ai,j ≤ 109, все значения ai,1 различны

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1102 ≤ n ≤ 10полная
272 ≤ n ≤ 2 ⋅ 105, k = 1первая ошибка
3152 ≤ n ≤ 2 ⋅ 105,
для всех t все ai, t различны
2первая ошибка
4152 ≤ n ≤ 2 ⋅ 105, 1 ≤ k ≤ 22первая ошибка
5262 ≤ n ≤ 400, 1 ≤ k ≤ 71первая ошибка
6272 ≤ n ≤ 2 ⋅ 105, 1 ≤ k ≤ 71, 2, 3, 4, 5первая ошибка

Пояснения к примерам

В первом примере пары имеют следующие параметры (8,6) − (3,1), (1,5) − (7,2), (6, 3) − (4,7). При указанном разбиении на пары подойдут, например, значения b1 = 4, b2 = 4,

Примеры тестов

Стандартный вход Стандартный выход
1
6 2
8 6
1 5
6 3
3 1
4 7
7 2
YES
1 4
2 6
3 5
2
4 3
1 -1 -1
2 1 1
3 -1 1
4 1 -1
NO

0.118s 0.017s 13