Trao đổi sách

Điểm: 2,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

Dạng bài

Ngôn ngữ cho phép

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

Có $n$ học sinh, ban đầu mỗi học sinh giữ một cuốn sách khác nhau. Vào cuối mỗi ngày, học sinh thứ $i$ đưa cuốn sách mình đang giữ cho học sinh $p_{i}$ (nếu $p_{i} = i$ thì cuốn sách ở lại với chính học sinh $i$ ). Dãy $p_{1}, p_{2}, \dots, p_{n}$ là một hoán vị của $1, 2, \dots, n$ và không thay đổi qua các ngày.

Với mỗi học sinh $i$ , hãy xác định số ngày ít nhất để cuốn sách ban đầu của học sinh $i$ quay trở lại với chính học sinh đó.

Bạn cần trả lời $q$ truy vấn độc lập.

Dữ liệu vào

Dòng đầu chứa một số nguyên $q$ — số truy vấn.
Mỗi truy vấn gồm hai dòng:
- Dòng đầu chứa số nguyên $n$ — số học sinh.
- Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ tạo thành một hoán vị của $1, 2, \dots, n$ .

Dữ liệu ra

Với mỗi truy vấn, in ra $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ trên một dòng, trong đó $a_{i}$ là số ngày ít nhất để cuốn sách của học sinh thứ $i$ quay trở lại với học sinh đó.

Ràng buộc

$1 \leq q \leq 200$
$1 \leq n \leq 200$
$1 \leq p_{i} \leq n$ , các $p_{i}$ đôi một phân biệt.

Ví dụ

Input	Output	Giải thích
2 5 1 2 3 4 5 3 2 3 1	1 1 1 1 1 3 3 3	Truy vấn 1: $p$ là hoán vị đồng nhất, mỗi cuốn sách quay lại sau đúng $1$ ngày. Truy vấn 2: $1 \to 2 \to 3 \to 1$ , ba học sinh tạo thành một vòng độ dài $3$ .
2 4 3 4 1 2 5 5 1 2 4 3	2 2 2 2 4 4 4 1 4	Ở truy vấn 1, cặp $(1, 3)$ và $(2, 4)$ tạo hai vòng độ dài $2$ . Ở truy vấn 2, các học sinh $1, 5, 3, 2$ tạo vòng độ dài $4$ , còn học sinh $4$ là điểm bất động (vòng độ dài $1$ ).

Bình luận

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