Artist in Agony
You, an artist, prepared a sufficient number of balls and also strings to link them for your artwork. Balls are to be given sequential numbers eventually, but only one of the balls is given number 1 at the beginning. No other balls are numbered and no balls are linked to any other balls yet.
An artwork is created by carrying out either of the following actions repetitively.
Note that, as initially only one ball is numbered, you have to start with the replication action.
Figure H-1 shows the process of artwork creation of the second dataset in Sample Input.
Figure H-1: Artwork creation example
Being a perfectionist as with all the real artists, you cannot stand imperfect works. When you find a work unsatisfactory, you have to destroy it completely as quick as possible by tearing off all the links in it. You grab some of the numbered balls in one hand, the rest in the other hand, and pull them apart tearing off all the strings linking the balls in your right hand and the balls in your left hand. If all the strings linking the balls are torn off by doing this operation just once, your destruction is successful. Conversely, any remaining links between two balls in one hand mean that the destruction is a failure.
Figure H-2 shows the work of the second dataset in Sample Input being destroyed. To destroy the work, you have to grab three or more balls in each of your hands.
Figure H-2: Destructing the artwork described above
Given the sequence of actions that created the work, judge whether you can destroy it in the way described above. If you can, find the minimum number of balls you have to grab in your left hand. You may grab an arbitrary number of balls in your right hand.
The input consists of multiple datasets, each in the following format.
m is the number of actions you have carried out. m is a positive integer and does not exceed 300.
The i-th action ai (i = 1, ..., m) is given by either of the following forms.
The end of the input is indicated by a line containing a zero. The number of datasets does not exceed 100.
For each of the datasets, output one line containing an integer. If you can destroy the work in the way described above, output the minimum number of balls you need to grab in your left hand. Otherwise, output −1.
3 COPY LINK 1 2 COPY 8 COPY COPY LINK 1 2 LINK 1 3 LINK 1 3 COPY LINK 5 6 LINK 3 6 5 COPY LINK 1 2 COPY LINK 1 3 LINK 2 3 2 COPY COPY 0
Output for the Sample Input
2 3 -1 0