Problem Description

In the design of relational database tables, the term "functional dependency" (FD) is used to represent relationships between different domains. A functional dependency describes the relationship between the values of domains in one set and the values of domains in another set. The notation $X \to Y$ is used to indicate that once the domains in set $X$ are assigned values, the domains in set $Y$ can be determined accordingly. For example, a data table contains domains such as "Social Security Number" ($S$), "Name" ($N$), "Address" ($A$), and "Phone" ($P$), and each person corresponds to a unique $S$ value. Based on domain $S$, the values of domains $N$, $A$, and $P$ can be determined. This is denoted as $S \to \{N,A,P\}$.

Write a program to identify all redundant dependencies in a set of dependencies. A dependency is redundant if it can be derived from other dependencies in the set. For example, if the set includes dependencies $A \to B$, $B \to C$, and $A \to C$, then the third dependency is redundant because domain $C$ can be derived from the first two dependencies (domain $A$ determines the value of domain $B$, and domain $B$ determines the value of domain $C$). In dependencies $A \to B$, $B \to C$, $C \to A$, $A \to C$, $C \to B$, and $B \to A$, all dependencies are redundant.

You are now required to write a program to identify redundant dependencies from the given set of dependencies.

Input Format

The first line is an integer $n$ not exceeding $100$, which represents the number of functional dependencies in the file.

Each subsequent line is a unique functional dependency, containing a non-empty list of domains separated by the characters - and >. The list includes uppercase letters. The data lines of the functional dependencies do not include spaces or tabs and do not contain "trivial" redundant dependencies (such as $A \to A$). Although the file does not number the functional dependencies, their order corresponds to the numbers $1$ to $n$.

Output Format

Each line outputs a redundant dependency and a sequence of other dependencies to demonstrate that the dependency is redundant. The format is FD x is redundant using FDs: p1 p2 ... pk, where $x$ is the number of the redundant dependency, and $p1, p2, ..., pk$ is the sequence of dependencies used to prove that $x$ is redundant.

If multiple sequences of functional dependencies can be used to demonstrate that a dependency is redundant, output the shortest proof sequence.

If there are no redundant dependencies among these functional dependencies, output No redundant FDs.

Sample Input and Output

Input Sample #1

3
A->BD
BD->C
A->C

Output Sample #1

FD 3 is redundant using FDs: 1 2

Input Sample #2

6
P->RST
VRT->SQP
PS->T
Q->TR
QS->P
SR->V

Output Sample #2

FD 3 is redundant using FDs: 1
FD 5 is redundant using FDs: 4 6 2

Notes

Explanation of Sample 1

Dependency $3$ is redundant. Because $A \to C$ can be derived using the first two dependencies $A \to \{B,D\}$ and $\{B, D\} \to C$.

见题面 Input 部分

见题面 Output 部分