#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 barns (), of which () distinct pairs of barns are connected. First, Annabelle assigns each barn a distinct integer label in the range , and observes that the barns with labels are connected in a cycle, in that order. That is, barns and are connected for all , and barns and are also connected. All are distinct. Next, Bessie also assigns each barn a distinct integer label in the range and observes that the barns with labels are connected in a cycle, in that order. All 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 and . The next line contains . The next line contains .
输出格式
The maximum number of fixed points.
数据范围
Inputs 4-5: Inputs 6-8: 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.