Bessie đang cố trốn khỏi những người nông dân. Những người nông dân sở hữu \(N\) (\(2 \le N \le 5 \cdot 10^5\)) trang trại, với một con đường một chiều nối trang trại thứ \(i\) đến trang trại thứ \(a_i\) (\(1 \le i \le N\), \(a_i \neq i\)). Có \(F\) (\(1 \le F \le N\)) người nông dân và người nông dân thứ \(i\) ban đầu đứng tại trang trại \(s_i\) (\(1 \le s_i \le N\), mọi \(s_i\) đôi một khác nhau). Tại mỗi bước thời gian, mỗi người nông dân đi theo con đường ở trang trại hiện tại của mình để đến trang trại tiếp theo. Bessie bị bắt nếu có bất kỳ lúc nào cô ở cùng một trang trại với một người nông dân.

Giả sử Bessie bắt đầu tại một trang trại \(b\). Tại mỗi bước thời gian, cô có hai lựa chọn: nghỉ lại (ở nguyên tại trang trại hiện tại) hoặc đi theo con đường để đến trang trại tiếp theo. Nếu chọn di chuyển, cô di chuyển đồng thời với những người nông dân. Bessie phải lựa chọn các bước di chuyển sao cho cô không bị bất kỳ người nông dân nào bắt tại bất kỳ thời điểm hữu hạn nào.

Với mỗi trang trại xuất phát \(b\) (\(1 \le b \le N\)), hãy tìm số lần lớn nhất Bessie có thể chọn nghỉ lại nếu cô bắt đầu tại trang trại \(b\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(F\), lần lượt là số trang trại và số người nông dân.

Dòng thứ hai chứa \(a_1 \ldots a_N\), mô tả con đường một chiều đi ra từ mỗi trang trại.

Dòng thứ ba chứa \(s_1 \ldots s_F\), vị trí xuất phát của mỗi người nông dân.

Dữ liệu ra

In ra \(N\) dòng; dòng thứ \(b\) gồm một số nguyên duy nhất biểu thị số lần lớn nhất Bessie có thể chọn nghỉ lại nếu cô bắt đầu tại trang trại \(b\). Nếu Bessie không có cách nào để tránh bị bắt tại mọi thời điểm hữu hạn, in ra \(-1\). Nếu Bessie có thể nghỉ lại vô hạn lần, in ra \(-2\).

Ví dụ

4 1
2 1 4 3
1

-1
0
-2
-2

Phân nhóm

• Test 2: \(N \le 50\).
• Các test 3–10: \(N \le 2000\).
• Các test 11–20: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Gold Division — The Chase. Tác giả: Alex Liang.
https://usaco.org/index.php?page=viewproblem2&cpid=1571