Đối Chiếu Chu Trình

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John quản lý $N$ chuồng bò, trong đó $K$ chuồng được nối thành một chu trình (mỗi chuồng trong chu trình nối với đúng 2 chuồng khác trong chu trình). Không có hai chuồng nào ngoài chu trình được nối với nhau.

Annabelle gán nhãn $1$ đến $N$ cho các chuồng và quan sát thấy các chuồng có nhãn $a_{1}, a_{2}, \dots, a_{K}$ tạo thành chu trình theo thứ tự đó. Bessie độc lập gán nhãn $1$ đến $N$ cho các chuồng và quan sát thấy các chuồng có nhãn $b_{1}, b_{2}, \dots, b_{K}$ tạo thành chu trình theo thứ tự đó.

Hãy tìm số lượng chuồng tối đa nhận được cùng nhãn từ cả Annabelle và Bessie.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $K$ ( $3 \leq K \leq N \leq 5 \cdot 10^{5}$ ).
Dòng $2$ : $K$ số nguyên $a_{1}, \dots, a_{K}$ — chu trình theo Annabelle.
Dòng $3$ : $K$ số nguyên $b_{1}, \dots, b_{K}$ — chu trình theo Bessie.

Dữ liệu ra

In ra một số nguyên — số lượng điểm cố định tối đa (chuồng có cùng nhãn).

Ràng buộc

Các test $2$ - $4$ : $N \leq 500$ .
Các test $5$ - $8$ : $N \leq 5000$ .
Các test $9$ - $15$ : Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
6 3 1 2 3 2 3 1	6	Annabelle gán nhãn 1,2,3 cho chu trình và 4,5,6 cho 3 chuồng ngoài. Bessie gán nhãn 2,3,1 cho chu trình. Nếu ta ánh xạ phù hợp, cả 6 chuồng có thể có cùng nhãn.
6 3 1 2 3 4 5 6	0	Không thể có chuồng nào có cùng nhãn vì các nhãn trong chu trình của hai người hoàn toàn khác nhau.
6 4 1 2 3 4 4 3 2 5	4	Tối đa 4 chuồng có thể có cùng nhãn.

Bình luận

Không có bình luận tại thời điểm này.