Cycle Correspondence

시간 제한2초메모리 제한1024 MB

요약

두 사람이 같은 K개의 헛간으로 이루어진 순환을 각자 다른 번호로 지정했을 때, 두 번호가 일치하는 헛간 수의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

Farmer John has $N$ barns ( $3\le N\le 5\cdot 10^5$ ), of which $K$ ( $3\le K\le 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 $a\_1,\dots,a\_K$ are connected in a cycle, in that order. That is, barns $a\_i$ and $a\_{i+1}$ are connected for all $1\le i\<K$ , and barns $a\_K$ and $a\_1$ are also connected. All $a\_i$ are distinct.

Next, Bessie also assigns each barn a distinct integer label in the range $\[1,N]$ and observes that the barns with labels $b\_1,\dots,b\_K$ are connected in a cycle, in that order. All $b\_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 $N$ and $K$ .

The next line contains $a\_1,\dots, a\_K$ .

The next line contains $b\_1,\dots, b\_K$ .

출력

The maximum number of fixed points.

예제3

예제 1
입력
```
6 3
1 2 3
2 3 1
```
예상 출력
```
6
```
예제 2
입력
```
6 3
1 2 3
4 5 6
```
예상 출력
```
0
```
예제 3
입력
```
6 4
1 2 3 4
4 3 2 5
```
예상 출력
```
4
```