P9978 [USACO23DEC] Cycle Correspondence S

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.

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$.

The maximum number of barns that can be assigned the same label.

### 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