Debug

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Description

Recently, Alice and Bob are working on a quantum computation model. In this model, all the variables are uncertain, and could be changed during any time. Fortunately, there are some techniques to construct the input data to make these variables show some certain feature at certain time. In other words, all condition statement can be controlled respectively from the input data.

To test some algorithms in this model, Alice wrote some codes to run on a prototype machine. As this machine requires a lots of resource to work, Alice wanted Bob to make a plan to debug these codes efficiently. Bob analysed the model and the machine, and found that in every unit of time, they can test exactly one program and exactly one input data. Bob want to minimize the time to debug the program. Now he asks for your help.

For your convenience, Bob would give you a simple edition of the codes. The new codes consist of some keywords, labels, and necessarily separative signs. Followings are formulas of sentence:
1) A label can be any combination of letters and number except keywords.
2) A label sentence is written as a label and a following colon without separative sign.
3) An atomic sentence is written as a keyword STATEMENT.
4) A jump sentence is written as a keyword GOTO and a following label, donating that the machine will jump to the label sentence which is with the same label. It is guaranteed that the each label sentence exists only once.
5) A condition sentence would be donated as a keyword IF and a following jump sentence. You can control the machine to execute the jump sentence or not through the input data. Also, you can have difference choose on the same condition sentence even if the input is the same.
6) A end sentence is written as a keyword END, donating that the code is over. End sentence exists once and at the end of a program. However, you can terminate the program at any position you want.
Additionally, separative signs could be space, tab or line break. Upper case letters and lower case letters are considered as different letters. The program would run starting at the first sentence and ending at the end sentence or your termination. To make sure the code is correct, you need to let every atomic sentence run at least once. Can you find the least time Bob need to debug this code?

Input

The first line is the number of test cases. For each test case, there is the code as described before. Each case contains no more than $100$ labels, $100$ atomic sentence, and $500$ others sentences.

Output

For each test case, output a line containing the minimum time Bob need. If there is no solution, output $-1$.

Sample Input

3 STATEMENT IF GOTO L1 STATEMENT GOTO L2 L1: STATEMENT L2: END STATEMENT IF GOTO L1 STATEMENT GOTO L2 L1: IF GOTO L1 L2: END STATEMENT L0: IF GOTO L1 STATEMENT GOTO L2 L1: STATEMENT L2: IF GOTO L0 END

Sample Output

2 1 1

Hint

jiangzijing2015

Source

2017中国大学生程序设计竞赛-哈尔滨站-重现赛(感谢哈理工)

提交代码