Cycle Correspondence

题目描述

农夫约翰有 $N$ 个谷仓（$3\le N\le 5\cdot 10^5$），其中有 $K$（$3\le K\le N$）对互不相同的谷仓之间有连接。

首先，Annabelle 给每个谷仓分配了一个互不相同的整数标签，范围在 $[1,N]$。她观察到，标签为 $a_1,\dots,a_K$ 的谷仓按此顺序连接成一个环。也就是说，对所有 $1\le i<K$，谷仓 $a_i$ 与 $a_{i+1}$ 相连，并且谷仓 $a_K$ 与 $a_1$ 也相连。所有 $a_i$ 互不相同。

接着，Bessie 也给每个谷仓分配了一个互不相同的整数标签，范围在 $[1,N]$。她观察到，标签为 $b_1,\dots,b_K$ 的谷仓按此顺序连接成一个环。所有 $b_i$ 互不相同。

有些（可能一个也没有，也可能全部）谷仓被 Annabelle 和 Bessie 分配了相同的标签。计算 Annabelle 与 Bessie 分配相同标签的谷仓数目的最大可能值。

输入格式

第一行包含 $N$ 和 $K$。 下一行包含 $a_1,\dots, a_K$。 下一行包含 $b_1,\dots, b_K$。

输出格式

相同标签的谷仓数（不动点）的最大值。

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

提示

Annabelle 和 Bessie 可能给每个谷仓都分配了相同的标签。 Annabelle 和 Bessie 不可能给任何谷仓分配相同的标签。 Annabelle 和 Bessie 可能给同一些谷仓分配了标签 $2,3,4,6$。 SCORING: Inputs 4-5: $N \le 8$ Inputs 6-8: $N \le 5000$ Inputs 9-15: 无额外限制 题目来源：Benjamin Qi

标签: USACO|2023|Silver

来源

USACO|2023|Silver