Problem 2. Cycle Correspondence

USACO 2023 December Contest, Silver

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

First, Annabelle assigns each barn a distinct integer label in the range $[1,N]$, and observes that the barns with labels $a_1,\dots,a_K$ are connected in a cycle, in that order. That is, barns $a_i$ and $a_{i+1}$ are connected for all $1\le i<K$, and barns $a_K$ and $a_1$ are also connected. All $a_i$ are distinct.

Next, Bessie also assigns each barn a distinct integer label in the range $[1,N]$ and observes that the barns with labels $b_1,\dots,b_K$ are connected in a cycle, in that order. All $b_i$ are distinct.

Some (possibly none or all) barns are assigned the same label by Annabelle and Bessie. Compute the maximum possible number of barns that are assigned the same label by Annabelle and Bessie.

INPUT FORMAT (input arrives from the terminal / stdin):

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 (print output to the terminal / stdout):

The maximum number of fixed points.

SAMPLE INPUT:

6 3
1 2 3
2 3 1

SAMPLE OUTPUT:

6

Annabelle and Bessie could have assigned the same label to every barn.

SAMPLE INPUT:

6 3
1 2 3
4 5 6

SAMPLE OUTPUT:

0

Annabelle and Bessie could not have assigned the same label to any barn.

SAMPLE INPUT:

6 4
1 2 3 4
4 3 2 5

SAMPLE OUTPUT:

4

Annabelle and Bessie could have assigned labels $2,3,4,6$ to the same barns.

SCORING: Inputs 4-5: $N \le 8$Inputs 6-8: $N \le 5000$Inputs 9-15: No additional constraints

Problem credits: Benjamin Qi