Problem Description

Farmer John has $N$ ($3 \le N \le 5 \cdot 10^5$) barns, with $K$ pairs of different barns connected together.

Initially, Annabelle assigns each barn a unique integer label within the range $[1, N]$, and finds that the barns labeled $a_1, \dots, a_K$ form a circular connection in order. In other words, for all $1 \le i < K$, barn $a_i$ is connected to barn $a_{i+1}$, and barn $a_K$ is also connected to barn $a_1$. All $a_i$ are distinct.

Then, Bessie also assigns each barn a unique integer label within the range $[1, N]$, and finds that the barns labeled $b_1, \dots, b_K$ also form a circular connection in order. All $b_i$ are distinct.

Some (possibly none or all) barns are assigned the same label by both Annabelle and Bessie. Calculate the maximum number of such barns.

Input Format

The first line contains $N$ and $K$.

The next line contains $a_1, \dots, a_K$.

The next line contains $b_1, \dots, b_K$.

Output Format

The maximum number of barns assigned the same label.

Sample Input and Output

Sample Input #1

6 3
1 2 3
2 3 1

Sample Output #1

6

Sample Input #2

6 3
1 2 3
4 5 6

Sample Output #2

0

Sample Input #3

6 4
1 2 3 4
4 3 2 5

Sample Output #3

4

Notes/Hints

Sample Explanation 1

Annabelle and Bessie can assign the same label to each barn.

Sample Explanation 2

Annabelle and Bessie cannot assign the same label to any barn.

Sample Explanation 3

Annabelle and Bessie can assign the labels $2, 3, 4, 6$ to the same barns.

Test Case Properties

• Test cases $4-5$ satisfy $N \le 8$.
• Test cases $6-8$ satisfy $N \le 5000$.
• Test cases $9-15$ have no additional restrictions.

见题面 Input 部分

见题面 Output 部分