사이클 대응

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

요약

두 개의 K개 헛간 사이클이 주어졌을 때, 두 배치에서 같은 번호를 받는 헛간의 최대 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 배열, 문자열 매칭, 해시맵
정답자: 아직 제출이 없습니다

문제

농부 존에게는 헛간이 $N$ 개 있고( $3 \le N \le 5 \times 10^5$ ), 그중 서로 다른 헛간 쌍 $K$ 개( $3 \le K \le N$ )가 연결되어 있다.

문제

애넷은 각 헛간에 $[1, N]$ 범위의 서로 다른 정수 번호를 하나씩 붙였고, 번호가 $a_1, \dots, a_K$ 인 헛간들이 이 순서대로 사이클을 이루며 연결되어 있다는 것을 확인했다. 즉 $1 \le i < K$ 인 모든 $i$ 에 대해 헛간 $a_i$ 와 $a_{i+1}$ 이 연결되어 있고, 헛간 $a_K$ 와 $a_1$ 도 연결되어 있다. 모든 $a_i$ 는 서로 다르다.

베시도 각 헛간에 $[1, N]$ 범위의 서로 다른 정수 번호를 하나씩 붙였고, 번호가 $b_1, \dots, b_K$ 인 헛간들이 이 순서대로 사이클을 이루며 연결되어 있다는 것을 확인했다. 모든 $b_i$ 는 서로 다르다.

애넷과 베시가 같은 번호를 붙인 헛간은 하나도 없을 수도, 일부일 수도, 전부일 수도 있다. 애넷과 베시가 같은 번호를 붙인 헛간 수의 최댓값을 구하라.

입력

첫 줄에 $N$ 과 $K$ 가 주어진다. 다음 줄에 $a_1, \dots, a_K$ 가 주어진다. 다음 줄에 $b_1, \dots, b_K$ 가 주어진다.

출력

같은 번호를 붙인 헛간 수의 최댓값을 출력한다.

예제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
```