У Фермера Джона \(N\) амбаров (\(3\le N\le 5\cdot 10^5\)), из которых
\(K\) (\(3\le K\le N\)) различных пар амбаров соединены.
Сначала Анабель назначила каждому амбару различную цифровую метку в интервале
\([1,N]\), и заметила, что амбары с метками \(a_1,\dots,a_K\) соединены в цикл,
в этом порядке. То есть, амбары \(a_i\) и \(a_{i+1}\) соединены для всех \(1\le i<K\),
и амбары \(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\).
ФОРМАТ ВЫВОДА (на экран):
Максимальное количество одинаковых назначений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
1 2 3
2 3 1
|
6
|