사이클 대응 (Cycle Correspondence) timer 1s memory 1024MB

농부 존은 N개의 헛간을 가지고 있습니다 (3≤N≤5⋅10^5), 그 중 K (3≤K≤N)개의 서로 다른 헛간 쌍이 연결되어 있습니다.

먼저, 애나벨은 각 헛간에 [1,N] 범위의 서로 다른 정수 라벨을 지정하고, 라벨이 a_1,…,a_K인 헛간이 순환 연결되어 있다는 것을 관찰합니다. 즉, 모든 1≤i<K에 대해 헛간 a_i와 a_{i+1}이 연결되어 있으며, 헛간 a_K와 a_1도 연결되어 있습니다. 모든 a_i는 서로 다릅니다.

다음으로, 배씨는 각 헛간에 [1,N] 범위의 서로 다른 정수 라벨을 할당하고, 라벨이 b_1,…,b_K인 헛간이 순환 연결되어 있다는 것을 관찰합니다. 모든 b_i는 서로 다릅니다.

애나벨과 배씨에 의해 동일한 라벨이 할당된 헛간이 있을 수도 있고 없을 수도 있습니다. 애나벨과 배씨에 의해 동일한 라벨이 할당된 헛간의 최대 가능한 수를 계산하세요.

[original]

Farmer John has N barns (3≤N≤5⋅10^5), 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.