URI Online Judge | 1326

Chemistry

By Guilherme Ottoni Brazil

Timelimit: 2

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:

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:

Input

The input consists of several test cases. Each test case starts with a line containing a single integer R, indicating the number of reactions to be considered (1 <= R <= 5000). The following R lines are of the form:

S1 + S2 → S3

Describing a reaction that consumes S1 and S2 and produces S3 as a result. The names of all substances are case-sensitive alphanumeric strings of size at most 5. A test case with R = 0 indicates the end of the input.

Output

For each test case in the input your program must produce one line, containing the string ‘PRODUCT requires N containers’, where PRODUCT is the final substance and N is the number of containers needed to produce it.

Sample Input Sample Output

1
2H + O -> Water
5
A + B -> T1
C + D -> T2
E + F -> T3
T2 + T3 -> T4
T4 + T1 -> P
3
a + b -> ab
ab + c -> abc
abc + d -> abcd
0

Water requires 1 containers
P requires 2 containers
abcd requires 1 containers