Farmer John has N barns (3≤N≤5⋅105), of which K (3≤K≤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 a1,…,aK are connected in a cycle, in that order. That is, barns ai and ai+1 are connected for all 1≤i<K, and barns aK and a1 are also connected. All ai are distinct.
Next, Bessie also assigns each barn a distinct integer label in the range [1,N] and observes that the barns with labels b1,…,bK are connected in a cycle, in that order. All bi 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 (pipe stdin):
The first line contains N and K.
The next line contains a1,…,aK.
The next line contains b1,…,bK.
OUTPUT FORMAT (pipe 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≤8
Inputs 6-8: N≤5000
Inputs 9-15: No additional constraints
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
