Problem E
Animal Classification
Alice and Bob are biologists. They like to group animals using classification trees. A classification tree is a binary tree where the leaves are labeled by the animals.
For example, Figure 1 below shows the classification of
![\includegraphics[width=0.5\textwidth ]{example.png}](/problems/animal/file/statement/en/img-0001.png)
As you can observe, Alice and Bob classify the animals
differently. Carol is interested to know the number of common
groups between the classifications of Alice and Bob. For the
above example, there are
Carol usually counts the number of common goups by hand. On
one day, an outer space alien came to our earth. He asked Alice
and Bob to classify aliens in outer space. The number
Input
The input consists of three lines:
-
one line with one integer
( ) -
the classification tree of Alice
-
the classification tree of Bob
Note that both classification trees are leaf-labeled by
Output
Output one line with a single integer that represents the number of common groups between Alice and Bob’s classification trees.
Sample Input 1 | Sample Output 1 |
---|---|
5 ((3,(1,(5,2))),4) (((5,1),(2,3)),4) |
7 |
Sample Input 2 | Sample Output 2 |
---|---|
10 (1,(2,(3,(4,(5,(6,(7,(8,(9,10))))))))) (((((((((1,2),3),4),5),6),7),8),9),10) |
11 |
Sample Input 3 | Sample Output 3 |
---|---|
10 (10,(9,(8,(7,(6,(5,(4,(3,(2,1))))))))) (((((((((1,2),3),4),5),6),7),8),9),10) |
19 |