Девичник
Чтобы отпраздновать 100-летний юбилей Университета Цинхуа, n девушек планируют устроить вечеринку. Они мастера в пении и танцах и предпочитают выступать в группах. В их плане предусмотрена сцена и ряд сидений. Когда группе девушек нужно выступить, они встают со своих мест и идут на сцену. После выступления они возвращаются на свои места (они не меняются местами, так как у каждой девушки много личных вещей на её месте).
Они хотят, чтобы этот процесс выглядел эффектно, поэтому для каждого выступления места актрис должны быть последовательными. Например, если есть 4 девушки, и выступают девушки 1, 2 и 4, то они не могут сидеть в порядке 1-2-3-4, так как, когда девушки 1, 2 и 4 встают, странно видеть не-актрису (девушку 3), сидящую между девушками 2 и 4.
Как я уже упоминал, они очень хороши в пении и танцах, поэтому им удалось придумать множество комбинаций. Теперь они немного обеспокоены: есть ли способ рассадить всех девушек так, чтобы вышеуказанное требование было выполнено (т.е. для каждой комбинации места актрис были последовательны).
Как хороший программист, вы решаете (я знаю, что на самом деле вас заставили, но...) написать программу, которая может вычислить количество вариантов рассадки. Поскольку девушки постоянно придумывают новые комбинации, ваша программа должна уметь считывать новые комбинации и соответственно корректировать ответ. Когда существует лишь несколько возможных вариантов (т.е. не более k допустимых решений), ваша программа должна вывести все из них.
Входные данные
Есть несколько тестов. Первая строка содержит три целых числа n, m, k (1 ≤ n, m, k ≤ 200), где n — количество девушек, m — количество комбинаций, и k — параметр, описанный выше. Каждая из следующих m строк содержит набор целых чисел, заканчивающийся нулем. Эти целые числа — это идентификаторы девушек в комбинации (девушки пронумерованы от 1 до n). Ввод заканчивается концом файла (EOF). Размер входного файла не превышает 1 МБ.
Выходные данные
Для каждой новой комбинации выведите количество вариантов рассадки, после учета этой комбинации. Если нет способа, выведите 0 и игнорируйте комбинацию. Если существует не более k способов, выведите их по одному в строке, в лексикографическом порядке.