Chemistry

International Chemical Products Company (ICPC) is a company known world-wide for its good and affordable products, which include shampoos, cleaning products, bug-killing products, and even some types of vaccines. The ICPC engineers are always researching new ways of reducing their products’ manufacturing costs, without lowering their quality.

One of their engineers, Mr. Poucher, has a new idea to reduce the cost, which aims at reducing the number of containers necessary to hold the substances during the sequence of chemical reactions to obtain a final substance. These final substances are obtained through a sequence of reactions of the form X + Y → Z, where X and Y are either initial substances or intermediate substances that were already generated from previous reactions. These reactions are done inside a reaction container, which once emptied can be cleaned up and used again. The process for generating a final substance can be described via a sequence of two simple operations:

• Put an available substance in an empty reaction container C;
• Perform the reaction X + Y → Z either by putting X in the reaction container holding Y, or by putting Y in the reaction container containing X. The order does not affect the end result of the reaction.

What Mr. Poucher noticed was that by choosing smartly the sequence of reaction, ICPC could drastically cut out on the number of reaction containers needed in the company. For example, consider the following sequence of chemical reactions used to obtain final substance P:

1) A + B -> T1
2) C + D -> T2
3) E + F -> T3
4) T2 + T3 -> T4
5) T4 + T1 -> P

In this example, A, B, C, D, E, and F are the initial substances (only appear on the left side of reactions), T1, T2, T3 and T4 are the intermediate substances (appear on the left side of at least one reaction, and exactly once on right side of some other reaction) and P is the final substance (only appears on the right side of a single reaction, which will be the last one listed).
If the sequence of reactions is performed as given then three reaction containers are necessary in order to produce the final substance P:

Containers
Operations C1 C2 C3

put A in C1: A - -
add B to C1: T1 - -
put C in C2: T1 C -
add D to C2: T1 T2 -
put E in C3: T1 T2 E
add F to C3: T1 T2 T3
put T2 in C3: T1 - T4
put T4 in C1: P - -

Note, however, that if the reactions are performed in the sequence 2, 3, 4, 1, 5, two reaction containers are sufficient:

Containers
Operations C1 C2

put C in C1: C
add D to C1: T2
put E in C2: T2 E
add F to C2: T2 T3
put T2 in C2: - T4
put A in C1: A T4
add B to C1: T1 T4
put T1 in C2: - P

You have been hired by ICPC, and your task is to create a computer program to determine the minimum number of reaction containers necessary to perform the sequence of reactions needed to obtain the final substance.

You should assume that:

• The reaction producing the final substance is the last listed, and the reaction producing an intermediate substance will always precede reactions where that intermediate substance is used.
• A sequence of reactions producing the final substance is always possible.
• ICPC has an unlimited supply of initial substances.
• At the beginning of the production process, each initial substance is in a storage container, used to hold all ICPC stock of this substance. Such containers cannot be used as reaction container to hold intermediate products of reactions.
• All the reaction containers are large enough to hold all the resulting substances.
• The amount of substance generated by a single reaction is just enough to be used as input to a single other reaction. For instance, if an intermediate product Z is necessary as input for two different reaction, this product must be produced twice.
• Every reaction uses exactly two distinct substances and generates also a distinct substance, i.e. all the reaction have the form X + Y ! Z, where X, Y and Z are all distinct.