One of the important concepts used in the theory of algorithms, is recursion. Informally, it can be defined as the use of the description of the object itself. When it comes to procedure, the process, it shall directly or indirectly (through other procedure) calls itself.
Recursion is a very "powerful" method of constructing algorithms, but is fraught with some danger. For example, carelessly written by a recursive procedure may enter into an infinite recursion, that is never complete their execution (in fact, end with the implementation of a stack overflow).
Since the recursion can be indirect (procedure calls itself through other procedures), the problem is determining whether a particular procedure is recursive, can be quite complex.
Consider a program consisting of n processes
Pn. Suppose that for each procedure known procedures that it may cause. Procedure P is potentially recursive if there exists a sequence of procedures
Qk = P and for i = 1 ... k procedure
Qi-1 can cause the procedure
Need to write a program that will determine for each of the defined procedures, whether it is potentially recursive.
The first line contains the number n (1 ≤ n ≤ 100) of procedures in the program. This is followed by n blocks, describing the procedure. Blocks are separated by rows, each of which contains 5 characters "*" (asterisk).
Description of the procedure starts with the line containing its identifier, consisting only of the small Latin letters and digits. Identifier can begin with both the letter and with the numbers. The length of the identifier from 1 to 100 characters. Next is a string containing the number of k (k ≤ n) - the number of procedures that may be caused by the described procedure. Follow k rows contain the identifiers of these procedures - one ID per line.
Different procedures have different IDs. However, no procedure can not call a procedure which is not described in the input.
For each procedure, which is present in the input, in the order in which they are listed in the input, you must bring a separate line in the name of the procedure followed by a colon, a space and then the word YES, if the procedure is potentially recursive, or the word NO otherwise.
3 p1 2 p1 p2 ***** p2 1 p1 ***** p3 1 p1
p1: YES p2: YES p3: NO