Bạn là giáo viên tại trường mẫu giáo Little Coders mới mở. Lớp có \(N\) em, mỗi em có một mã học sinh khác nhau từ 1 đến \(N\). Mỗi em có đúng một người bạn thân nhất (BFF), và bạn biết BFF của từng em. Quan hệ này không nhất thiết hai chiều: B là BFF của A không có nghĩa A là BFF của B.

Kế hoạch bài học ngày mai có một hoạt động mà người tham gia phải ngồi thành vòng tròn. Bạn muốn tạo vòng tròn lớn nhất có thể sao cho mỗi em ngồi ngay cạnh BFF của mình, ở bên trái hoặc bên phải. Những em không ở trong vòng sẽ chỉ quan sát.

Số trẻ lớn nhất có thể ngồi trong vòng là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu là \(N\), tổng số trẻ. Dòng thứ hai chứa \(N\) số \(F_1,F_2,\ldots,F_N\), trong đó \(F_i\) là mã học sinh của BFF của em có mã \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, với \(x\) bắt đầu từ 1 và \(y\) là số trẻ lớn nhất có thể xếp thành vòng sao cho mỗi em ngồi cạnh BFF của mình.

Ràng buộc

• \(1\le T\le100\).
• \(1\le F_i\le N\) với mọi \(i\).
• \(F_i\ne i\) với mọi \(i\) (không ai là BFF của chính mình).

Phân nhóm

• Test Set 1 (Visible): \(3\le N\le10\).
• Test Set 2 (Hidden): \(3\le N\le1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
4
2 3 4 1
4
3 3 4 1
4
3 3 4 3
10
7 8 10 10 9 2 9 6 3 3

Case #1: 4
Case #2: 3
Case #3: 3
Case #4: 6

Nguồn

Google Code Jam 2016, Vòng 1A, bài BFFs.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.