Description

The example above shows that scoring by counting how many items are in the correct absolute positions is unfair. Is there a better way? One possibility is to find the longest subsequence (not necessarily consecutive) of items that are in the correct relative order. This is still not the best solution: if one item is moved by only one position from the correct order, then even though the ordering is almost correct, the score may drop to zero. Therefore, Mirko-wan suggested the following grading method to his history teacher:

For every pair of items among the $n$ items, if the relative order of the two items is correct, the student gets $1$ point. In other words, the score is the number of item pairs that the student ordered correctly. Of course, the maximum score is the total number of pairs, which is $\dfrac{n(n-1)}{2}$.

Using this method, given the correct order of $n$ items and the order provided by Mirko-wan, compute the score Mirko-wan receives.

Input Format

The input consists of three lines.

The first line contains an integer $n$, the number of items.
The second line contains $n$ strings, the correct order of the $n$ items.
The third line contains $n$ strings, the order of the $n$ items given by Mirko-wan.

Output Format

Output in the format a/b, where:

• $a$ is the score Mirko-wan receives according to the given order and the new scoring method.
• $b$ is the maximum possible score under the new scoring method.

Note that in this problem, do not reduce the fraction.

3
alpha beta gamma
alpha gamma beta

2/3

5
naboo geonosis yavin hoth endor
geonosis yavin hoth endor naboo

6/10

Hint

Sample 1 Explanation

For sample $1$, the item pairs that give Mirko-wan points are $(\texttt{alpha},\texttt{beta})$ and $(\texttt{alpha},\texttt{gamma})$.

Constraints

For all testdata, $2\leqslant n\leqslant 2500$. The string length is in $[3,15]$, consisting only of lowercase English letters, and all items are distinct.

Source

This problem is from COCI 2012-2013 CONTEST 3 T2 POREDAK. With the original testdata configuration, the full score is $80$ points.

Translated and整理 (zhengli) provided by Eason_AC.

Translated by ChatGPT 5