Proofs

You are teaching discrete math. You have done your best to teach your students about axioms and inference rules, proofs and theorems. Sometimes the students write beautiful proofs that Fermat would be proud of but sometimes, also like Fermat, their proofs are not quite right. You are getting a little tired of hunting through some of these so-called “proofs” for the magic tricks that let them prove $1 = 2$ and had the great idea to write a computer program to speed things up!

Because this is the first class in proof-based mathematics, you have started your students off with a simple proof system. All proof lines consist of a list of assumptions, an arrow, and a conclusion. If there are no assumptions, the conclusion is an axiom. A line of the proof is valid if and only if all assumptions were conclusions of previous lines. Sometimes the students derive a conclusion more than once just to be extra sure it is true, and that is perfectly all right!

The first line of input consists of an integer $1 \le n \le 400\, 000$, the number of
lines in the “proof”. Then follow the $n$ lines of the “proof”. Each line
has $0 \le a \le 5$
assumptions, followed by an arrow (the string “`->`”), followed by one conclusion. All
assumptions and conclusions consist of $1 \le c \le 5$ uppercase alphabetic
characters. The assumptions, arrow, and conclusion are all
separated by single spaces.

If every line is correct output “`correct`”. Otherwise, output the number of the
first line with an error (line numbers start at $1$).

Sample Input 1 | Sample Output 1 |
---|---|

3 -> ALICE -> BOB ALICE BOB -> CARL |
correct |

Sample Input 2 | Sample Output 2 |
---|---|

1 A -> B |
1 |