Стек - тип данных, представляющий собой список элементов, организованных по принципу "последним пришёл - первым ушёл". В большинстве архитектур компьютерных систем стек применяется для организации вызова подпрограмм, поскольку лучше всего подходит для
обеспечения работы рекурсии.
Фирма Хардсофт занялась разработкой инновационного процессора с переменной длиной кодов команд. Одновременно одно из её подразделений начало работу над компилятором для нового процессора. Им удалось создать алгоритм предсказания запуска той или иной подпрограммы на основе исходного кода, и теперь разработчики хотят на основе полученной информации научиться
определять оптимальный размер стека.
Вам требуется помочь им составить программу для получения всех возможных цепочек вызовов подпрограмм на основе результатов работы их алгоритма.
Входные данные
в первой строке записано натуральное число N, не превышающее 10 - максимальная глубина вложенности вызовов подпрограмм. Начиная со второй строки, идёт протокол работы алгоритма предсказания запуска подпрограмм, который заканчивается строкой, состоящей из одной точки.
Пример протокола:
PROC A
ENDPROC
PROC B
CALL A
ENDPROC
PROC MAIN
CALL B
ENDPROC
.
Описание подпрограммы в нём начинается со слова PROC, после которого через идёт имя из латинских букв, длина которого не превышает 20 символов.
Внутри подпрограммы могут указываться вызовы других подпрограмм с помощью слова CALL и через пробел - имени вызываемой подпрограммы.
Описание подпрограммы завершается словом ENDPROC.
Описания подпрограмм не могут пересекаться и быть вложенными. Первой всегда выполняется подпрограмма MAIN и она всегда есть в протоколе.
Выходные данные
в первой строке - количество выявленных цепочек, в последующих строках - цепочки вызовов, соответствующие исходному протоколу. Каждая цепочка должна быть выведена с новой строки, а имена подпрограмм в ней должны быть приведены в том порядке, в котором
происходят их вызовы, и записаны через пробел. Имя MAIN выводить не нужно, работа главной подпрограммы в подсчёт вложенности вызовов не входит.
Цепочки должны быть выведены в том порядке, в котором возможен их вызов при работе программы. Следует иметь в виду, что протокол составлен таким образом, что любой из указанных вызовов может состояться, а может не произойти. При этом вызов вложенных подпрограмм невозможен, если не вызвана вышестоящая подпрограмма.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
PROC A
CALL A
ENDPROC
PROC B
CALL A
ENDPROC
PROC MAIN
CALL B
ENDPROC
. |
4
B
B A
B A A
B A A A |
| 2 |
3
PROC A
CALL A
ENDPROC
PROC B
CALL A
ENDPROC
PROC C
ENDPROC
PROC MAIN
CALL A
CALL B
CALL C
ENDPROC
. |
15
A
A A
A A A
A A B
A A C
A B
A B A
A B C
A C
B
B A
B A A
B A C
B C
C |