Problem Description

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

At first, Annabelle assigns each barn an integer label in the range $[1,N]$, and she finds that the barns with labels $a_1,\dots,a_K$ form a cycle 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 an integer label in the range $[1,N]$, and she finds that the barns with labels $b_1,\dots,b_K$ also form a cycle connection in order. All $b_i$ are distinct.

Some (possibly none or all) barns are assigned the same label by both Annabelle and Bessie. Compute 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 that can be assigned the same label.

6 3
1 2 3
2 3 1

6

6 3
1 2 3
4 5 6

0

6 4
1 2 3 4
4 3 2 5

4

Hint

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Test Point Properties

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

Translated by ChatGPT 5