Time limit: 1.0s , Memory limit: 256M , Points: 0 (partial)
Một đồ thị có dạng cây nếu giữa hai đỉnh bất kỳ của đồ thị đều tồn tại duy nhất một đường đi đơn giữa chúng. Khoảng cách giữa hai đỉnh của cây được định nghĩa là số cạnh nằm trên đường đi giữa hai đỉnh đó.
Cho mảng gồm
số nguyên được đánh số từ
đến
. Nhiệm vụ của bạn hãy xác định xem có tồn tại ít nhất một cách xây dựng cây gồm
đỉnh thỏa mãn điều kiện sau hay không:
- Với mỗi
, khoảng cách lớn nhất từ đỉnh
đến một đỉnh khác của cây bằng chính xác
.
Input
- Dòng đầu tiên chứa số nguyên
là số test case
. Mỗi test case được mô tả như sau:
- Dòng đầu tiên chứa số nguyên
.
- Dòng thứ hai chứa
số nguyên của mảng
.
Output
- Với mỗi test case, in ra trên một dòng: "YES" nếu có tồn tại ít nhất một cách xây dựng cây thỏa mãn điều kiện đề bài, ngược lại in ra "NO".
Examples
Sample Input
2
3
2 2 2
4
2 1 2 2
Sample Output
NO
YES
Scoring
- Subtask
với
số điểm:
- Subtask
với
số điểm: Không có ràng buộc gì thêm
Notes
Ở test case thứ hai, có thể xây dựng một cây thỏa mãn điều kiện như trong hình sau:
![drawing](/media/martor/77d12fc2-bd1b-4bb0-8160-c4c1739550e8.jpg)
Comments