eolymp
bolt
Try our new interface for solving problems
Problems

Recursion

Recursion

Time limit 1 second
Memory limit 128 MiB

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 P[1], P[2], ..., P[n]. Suppose that for each procedure known procedures that it may cause. Procedure P is potentially recursive if there exists a sequence of procedures Q[0], Q[1], ..., Q[k], that Q[0] = Q[k] = P and for i = 1 ... k procedure Q[i-1] can cause the procedure Q[i].

Need to write a program that will determine for each of the defined procedures, whether it is potentially recursive.

Input data

The first line contains the number n (1n100) 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 (kn) - 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.

Output data

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.

Examples

Input example #1
3
p1
2
p1
p2
*****
p2
1 
p1
*****
p3
1
p1
Output example #1
p1: YES
p2: YES
p3: NO
Source 2008 XIX regional school olympiad in informatics, Vologda, Problem B