Разбиение на пары
Космические археологи обнаружили на планете в соседней звездной системе n древних артефактов, которые они пронумеровали от 1 до n. Каждый артефакт имеет k различных параметров, каждый параметр характеризуется целым числом. Артефакт i имеет параметры a[i,1], a[i,2], ... a[i,k]. Оказалось, что первые параметры у всех артефактов различны: для всех i ≠ j выполнено a[i,1] ≠ a[j,1], при этом другие параметры у артефактов могут совпадать.
Учёные также обнаружили текст, в соответствии с которым для активации артефактов их необходимо особым образом разбить на пары и совместить. Разбиение артефактов на пары является корректным, если для каждого t от 1 до k можно выбрать такое число b[t], что оно лежит на отрезке между значениями t-го параметра артефактов каждой пары. То есть, если артефакты i и j образуют пару, должно выполняться условие a[i,t] ≤ b[t] ≤ a[j,t] или условие a[i,t] ≥ b[t] ≥ a[j,t].
Теперь ученые хотят выяснить, верно ли расшифрован текст. Для этого необходимо проверить, существует ли корректное разбиение артефактов на пары. Каждый артефакт должен войти ровно в одну пару в разбиении.
Напишите программу, которая по описанию параметров артефактов определяет, можно ли разбить их на пары таким образом, чтобы для каждого параметра существовало значение, лежащее между значениями этого параметра артефактов каждой пары, и в случае положительного ответа выводит такое разбиение.
Входные данные
В первой строке заданы целые числа n и k (2 ≤ n ≤ 2 * 10^5, n чётно, 1 ≤ k ≤ 7) - количество артефактов и количество параметров. В следующих n строках задано по k целых чисел a[i,1], a[i,2], ..., a[i,k] - параметры артефактов (-10^9 ≤ a[i,j] ≤ 10^9, все значения a[i,1] различны).
Выходные данные
Выведите "NO", если требуемого разбиения на пары не существует.
В противном случае выведите "YES" в первой строке. Далее выведите n / 2 строк, в каждой строке выведите по два числа - номера артефактов, из которых следует составить пару. Каждый артефакт должен быть выведен ровно один раз.
Если существует несколько корректных разбиений артефактов на пары, разрешается вывести любое из них.