16737번 - Python Classes 다국어

Mr. Programmer has been busy working on his awesome startup project lately. The project was coded in Python. In the past few days, he was hugely refactoring the source code without any testing. After all changes have been made, he tried to run the project, but he figured out that the code is not executing properly anymore due to some cyclic dependencies created in his source code. He struggled a little bit moving things around only to know he is just messing up things even further. Maybe if I move all the classes to a single file I’ll be able to resolve the problem, he thought. But that plan didn’t work either. With a great frustration and feeling pressure to launch his project as soon as possible, he has finally decided to outsource the task of putting things in the correct order to algorithmic specialists.

The source code is a single Python file. It consists of a bunch of classes. Mr. Programmer doesn’t like multiple inheritances much, so each class in his code has at most one super class. As he does not want to leak the content of the classes, he has nulled out the contents and effectively replaced them with the “pass” command in Python. Therefore, when a class does not have a superclass, it looks like below:

class <CLASS_NAME>:
    pass

When a class has a superclass, it looks like below:

class <CLASS_NAME>(<SUPER_CLASS_NAME>):
    pass

In the above codes, CLASS_NAME and SUPER_CLASS_NAME are arbitrary Python identifiers. For further clarification look at the sample input.

We know that the file is executable if for each class having a super class, its superclass appears somewhere before the class in the file. Mr. Programmer doesn’t like too many changes to his file, so he wants to put the file in the correct order with the minimum number of changes. Each change is counted as cutting a single class (along with its content) and pasting it in some other position in the file. Help Mr. Programmer find the minimum number of changes to file so that the file becomes executable.

The input is a python file. It consists of some python classes separated by a single blank line. The classes in the input are exactly in the format described in the problem statement. Class identifiers only consists of English upper or lower case letters, and their length does not exceed 10 characters (for the sake of this problem you should not make any other assumptions about the identifiers). There are exactly 4 space characters before each “pass” command. There are at most 2, 000 classes in the file. It is guaranteed that all super classes are defined somewhere in the file, and no class is defined multiple times. Furthermore, a class is not its own superclass.

Print a single integer as the minimum number of changes that have to be made so that the file becomes executable, or -1 if it is not possible to do so.