Farmer John có \(N\) chuồng (\(3\le N\le 5\cdot 10^5\)), trong đó có \(K\) cặp chuồng đôi một khác nhau được nối với nhau (\(3\le K\le N\)).

Trước tiên, Annabelle gán cho mỗi chuồng một nhãn số nguyên khác nhau trong đoạn \([1,N]\) và quan sát thấy các chuồng mang nhãn \(a_1,\dots,a_K\) được nối thành một chu trình theo thứ tự đó. Tức là, các chuồng \(a_i\) và \(a_{i+1}\) được nối với nhau với mọi \(1\le i<K\), đồng thời \(a_K\) và \(a_1\) cũng được nối với nhau. Tất cả \(a_i\) đôi một khác nhau.

Tiếp theo, Bessie cũng gán cho mỗi chuồng một nhãn số nguyên khác nhau trong đoạn \([1,N]\) và quan sát thấy các chuồng mang nhãn \(b_1,\dots,b_K\) được nối thành một chu trình theo thứ tự đó. Tất cả \(b_i\) đôi một khác nhau.

Một số chuồng (có thể không có chuồng nào hoặc là tất cả các chuồng) được Annabelle và Bessie gán cùng một nhãn. Hãy tính số lượng lớn nhất có thể của các chuồng được Annabelle và Bessie gán cùng một nhãn.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

Dòng tiếp theo chứa \(a_1,\dots,a_K\).

Dòng tiếp theo chứa \(b_1,\dots,b_K\).

Dữ liệu ra

In số điểm bất động lớn nhất.

Ví dụ

6 3
1 2 3
2 3 1

6

6 3
1 2 3
4 5 6

0

6 4
1 2 3 4
4 3 2 5

4

Phân nhóm

• Dữ liệu 4–5: \(N\le 8\).
• Dữ liệu 6–8: \(N\le 5000\).
• Dữ liệu 9–15: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Silver — Cycle Correspondence: https://usaco.org/index.php?page=viewproblem2&cpid=1351

Tác giả bài toán: Benjamin Qi