Redundant Functional Dependencies

In relational database design, a functional dependency (FD) of the form \(X \to Y\) indicates that when the values for the set of attributes \(X\) are fixed, the values for the set \(Y\) are uniquely determined. For example, if a table has attributes Social Security Number (\(S\)), Name (\(N\)), Address (\(A\)) and Phone (\(P\)), and every person has a unique \(S\) such that \(S \to \{N, A, P\}\), then the value of \(S\) determines the values of \(N\), \(A\) and \(P\).

A dependency is said to be redundant if it can be derived from the other dependencies. For instance, given the dependencies \(A \to B\), \(B \to C\) and \(A \to C\), the dependency \(A \to C\) is redundant because \(A\) determines \(B\) which in turn determines \(C\).

Your task is to write a program that reads a set of functional dependencies and outputs all the redundant dependencies in the same order as input.

Input Format: The first line contains an integer \(n\) (where \(n \ge 2\)) representing the number of dependencies. Each of the following \(n\) lines contains a functional dependency in the format:

[ \texttt{X->Y} ]

where \(X\) and \(Y\) are non-empty strings of uppercase letters representing sets of attributes.

Note: A dependency \(X \to Y\) is redundant if, after removing it from the set, the closure of \(X\) (computed using the remaining dependencies) already contains all attributes in \(Y\).

inputFormat

The input begins with an integer \(n\) (number of dependencies). Each of the next \(n\) lines contains a dependency in the format "X->Y", where both \(X\) and \(Y\) are non-empty strings of uppercase letters.

outputFormat

Output all redundant dependencies in the same order as they appear in the input. Each redundant dependency should be printed on its own line. If there is no redundant dependency, print None.

sample

3
A->B
B->C
A->C

A->C