eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Рекурсия

Рекурсия

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Одним из важных понятий, используемых в теории алгоритмов, является рекурсия. Неформально её можно определить как использование в описании объекта самого себя. Если речь идёт о процедуре, то в процессе исполнении эта процедура напрямую или косвенно (через другие процедуры) вызывает сама себя.

Рекурсия является очень "мощным" методом построения алгоритмов, но таит в себе некоторые опасности. Например, неаккуратно написанная рекурсивная процедура может войти в бесконечную рекурсию, то есть никогда не закончить своё выполнение (на самом деле выполнение закончится с переполнением стека).

Поскольку рекурсия может быть косвенной (процедура вызывает сама себя через другие процедуры), то задача определения факта, является ли конкретная процедура рекурсивной, может быть достаточно сложна.

Рассмотрим программу, состоящую из n процедур P[1], P[2], ..., P[n]. Пусть для каждой процедуры известны процедуры, которые она может вызывать. Процедура P называется потенциально рекурсивной, если существует такая последовательность процедур Q[0], Q[1], ..., Q[k], что Q[0] = Q[k] = P и для i = 1 ... k процедура Q[i-1] может вызвать процедуру Q[i].

Требуется написать программу, которая определит для каждой из заданных процедур, является ли она потенциально рекурсивной.

Входные данные

Первая строка содержит количество процедур n (1n100) в программе. Далее следуют n блоков, описывающих процедуры. Блоки отделены друг от друга строками, каждая из которых содержит по 5 символов "\*" (звёздочка).

Описание процедуры начинается со строки, содержащий её идентификатор, состоящий только из маленьких букв латинского алфавита и цифр. Идентификатор может начинаться как с буквы, так и с цифры. Длина идентификатора от 1 до 100 символов. Далее идёт строка, содержащая число k (kn) - количество процедур, которые могут быть вызваны описываемой процедурой. Последующие k строк содержат идентификаторы этих процедур - по одному идентификатору в строке.

Различные процедуры имеют различные идентификаторы. При этом ни одна процедура не может вызвать процедуру, которая не описана во входе.

Выходные данные

Для каждой входной процедуры, в порядке, в каком они перечислены на входе, необходимо вывести в отдельной строке название процедуры, затем двоеточие, пробел, затем слово YES, если процедура является потенциально рекурсивной, или слово NO в противном случае.

Пример

Входные данные #1
3
p1
2
p1
p2
*****
p2
1 
p1
*****
p3
1
p1
Выходные данные #1
p1: YES
p2: YES
p3: NO
Источник 2008 XIX школьная областная олимпиада по информатике, Вологда, Задача B