Background

The testdata on Luogu is for non-commercial communication only and is not official testdata. Official judging link: https://www.cspro.org/.

The Jaccard similarity of two sets is defined as:

That is, the size of the intersection divided by the size of the union. When sets $A$ and $B$ are exactly the same, $Sim(A, B) = 1$, which is the maximum value; when their intersection is empty, $Sim(A, B) = 0$, which is the minimum value.

Problem Description

Besides doing simple word frequency statistics, Xiao P also wants to use Jaccard similarity to evaluate how similar two articles are. Specifically, each article consists of several English words, and each word contains only “uppercase and lowercase English letters”. For the given two articles, Xiao P first needs to extract their word sets $A$ and $B$, that is, remove duplicate words within each article. Then compute:

• $|A \cap B|$, i.e., how many different words appear in both articles;
• $|A \cup B|$, i.e., how many different words appear in total across the two articles.

Finally, dividing the former by the latter gives the similarity. Note that during the whole process, you should ignore letter case. For example, the, The, and THE should be treated as the same word.

Write a program to help Xiao P complete the first two steps, computing $|A \cap B|$ and $|A \cup B|$. Xiao P will do the final division by himself.

Input Format

Read from standard input.

There are three lines in total.

The first line contains two positive integers $n$ and $m$, representing the number of words in the two articles.

The second line contains $n$ space-separated words, representing the first article.

The third line contains $m$ space-separated words, representing the second article.

Output Format

Write to standard output.

There are two lines in total.

The first line outputs an integer $|A \cap B|$, i.e., how many different words appear in both articles.

The second line outputs an integer $|A \cup B|$, i.e., how many different words appear in total across the two articles.

3 2
The tHe thE
the THE

1
1

9 7
Par les soirs bleus dete jirai dans les sentiers
PICOTE PAR LES BLES FOULER LHERBE MENUE

2
13

15 15
Thou that art now the worlds fresh ornament And only herald to the gaudy spring
Shall I compare thee to a summers day Thou art more lovely and more temperate

4
24

Hint

Explanation for Sample 1

$A = B = A \cap B = A \cup B = \{\text{the}\}$

Explanation for Sample 2

$A = \{\text{bleus, dans, dete, jirai, les, par, sentiers, soirs}\} \quad |A| = 8$

$B = \{\text{bles, fouler, les, lherbe, menue, par, picote}\} \quad |B| = 7$

$A \cap B = \{\text{les, par}\} \quad |A \cap B| = 2$

Subtasks

• $80\%$ of the testdata satisfies: $n, m \le 100$ and all letters are lowercase.
• All testdata satisfies: $n, m \le 10^4$ and each word contains at most $10$ letters.

Translated by ChatGPT 5