Задача №111521. Тестирование программы
Вчера у Васи был счастливый день: он наконец дописал программу всей своей жизни! И, недолго думая, он тут же запустил ее на Самом Главном Тесте.
Программа Васи очень сложная, и потому работает она долго. Поэтому Вася пошел спать, а наутро, сегодня, обнаружил, что программа, вместо того, чтобы посчитать нужный Ответ, вылетела с непонятной ошибкой.
Вася понял, что напрасно он не тестировал программу. Ведь Самый Главный Тест очень сложный — в нем есть \(N\) отдельных подзадач, и каждую из них надо решить. Конечно, надо было бы начать тестирование с меньшего количества подзадач, но ведь Вася — очень умный программист! И он абсолютно уверен, что его программа корректно решила все подзадачи, кроме какой-то одной. Вот только Вася не знает, какой именно.
Вася может изменять Самый Главный Тест, отключая в нем те или иные подзадачи. Он надеется, что, если среди отключенных будет та подзадача, на которой его программа не работает, то получившийся тест его программа спокойно пройдет. Но вот проблема: программа работает долго, а подзадач много, и потому, если отключать задачи по одной, то придется очень долго искать нужную. А Вася очень хочет узнать, где ошибка, уже завтра!
К счастью, у Васи в распоряжении есть много компьютеров. Он может на некоторых из них запустить свою программу на каком-то тесте (т.е. на Самом Главном Тесте с некоторыми отключенными подзадачами), а назавтра посмотреть, какие программы завершились успешно, а какие нет, — и по результатам понять, какая подзадача создавала проблемы. Помогите Васе подобрать тесты для каждого из компьютеров, т.е. объясните ему, какие подзадачи в каком тесте он должен отключить, так, чтобы назавтра, узнав результаты работы программы на этих тестах, он смог бы уверенно определить, с какой подзадачей у него возникают проблемы (естественно, считая, что такая подзадача только одна, ведь Вася — очень умный программист!)
Учтите, что Васе не хочется делать лишнюю работу по запуску программ и определению их результата, поэтому он хочет минимизировать количество запусков (т.е. фактически количество компьютеров, ведь его программа настолько сложная, что на одном компьютере можно запустить только один экземпляр программы).
В первой и единственной строке входного файла находится одно целое число \(N\) — количество подзадач в Самом Главном Тесте (\(1 \le N \le 10^5\)).
В первой строке выходного файла выведите минимальное необходимое количество компьютеров \(M\). В последующих \(M\) строках выведите информацию о том, на каком тесте надо запускать программу на каком компьютере. А именно, в \(i\)-ую из них выведите последовательность чисел \(k_i\), \(b_{i1}\), \(b_{i2}\), ...., \(b_{ik_i}\), где \(k_i\) — количество подзадач, которые надо отключить в тесте, на котором будет работать программа на \(i\)-ом компьютере, а \(b_{ij}\) (\(1 \le j \le k_i\), \(1 \le b_{ij} \le N\)) — номера подзадач, которые надо отключать. Числа \(b_{ij}\) должны быть различны для каждого фиксированного \(i\).
Подзадачи нумеруются от 1 до \(N\).
В пределах одной строки подзадачи можете выводить в любом порядке. Если есть несколько оптимальных решений, выведите любое.
В примере:
- если ошибка возникала на первой подзадаче, то на всех трех компьютерах программа отработает верно, т.к. первая подзадача во всех тестах отключена;
- если ошибка возникала на второй подзадаче, то ошибочно сработает только первый компьютер;
- если ошибка возникала на третьей подзадаче, то ошибочно сработает только второй компьютер;
- если ошибка возникала на четвертой подзадаче, то ошибочно сработают первый и второй компьютеры;
- если ошибка возникала на пятой подзадаче, то ошибочно сработает только третий компьютер.
5
3 3 1 3 5 3 1 2 5 4 1 2 3 4