Задачі
Простая монотонность
Простая монотонность
Пусть есть некотороая булевая функция, определенная на некотором множестве булевых векторов размерности \textbf{K}. Один вектор является предшествующим по отношению к другому, если они различны и каждая координата первого вектора не больше чем соответствующая координата второго. Функция называется монотонной, если её значение на каждом векторе не меньше чем на любом предшествующем векторе. Требуется переопределить функцию в минимальном количестве векторов, чтобы она стала монотонной.
\InputFile
Два числа \textbf{N} и \textbf{k} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10}) --- количество векторов и размерность. Далее \textbf{N} строк по \textbf{k+1} числу в каждой --- булевый вектор и значение функции в нём. Все числа - \textbf{0} или \textbf{1}. Все вектора различны.
\OutputFile
В первой строке минимальное количество векторов, значение функции в которых необходимо изменить, чтобы она стала монотонной. Во второй строке номера этих векторов без повторений в любом порядке.
Вхідні дані #1
8 3 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0
Вихідні дані #1
2 1 8