#PU1351. USACO 2023 December Contest, Silver — Problem 2. Cycle Correspondence

USACO 2023 December Contest, Silver — Problem 2. Cycle Correspondence

USACO 2023 December Contest, Silver — Problem 2. Cycle Correspondence

题目描述

Farmer John has NN barns (3≤N≤5⋅1053\le N\le 5\cdot 10^5), of which KK (3≤K≤N3\le K\le N) distinct pairs of barns are connected. First, Annabelle assigns each barn a distinct integer label in the range [1,N][1,N], and observes that the barns with labels a1,…,aKa_1,\dots,a_K are connected in a cycle, in that order. That is, barns aia_i and ai+1a_{i+1} are connected for all 1≤i<K1\le i<K, and barns aKa_K and a1a_1 are also connected. All aia_i are distinct. Next, Bessie also assigns each barn a distinct integer label in the range [1,N][1,N] and observes that the barns with labels b1,…,bKb_1,\dots,b_K are connected in a cycle, in that order. All bib_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.

输入格式

The first line contains NN and KK. The next line contains a1,…,aKa_1,\dots, a_K. The next line contains b1,…,bKb_1,\dots, b_K.

输出格式

The maximum number of fixed points.

数据范围

Inputs 4-5: N≤8N \le 8 Inputs 6-8: N≤5000N \le 5000 Inputs 9-15: No additional constraints Problem credits: Benjamin Qi

样例

样例 1

6 3
1 2 3
2 3 1
6
Annabelle and Bessie could have assigned the same label to every barn.

样例 2

6 3
1 2 3
4 5 6
0
Annabelle and Bessie could not have assigned the same label to any barn.

样例 3

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