Đồ thị có ứng dụng rộng rãi trong tin học. Có nhiều cách biểu diễn đồ thị như dùng ma trận kề hoặc danh sách các đỉnh kề v.v…Một cách mô tả đồ thị là liệt kê bậc của các đỉnh. Bậc của một đỉnh là số cạnh xuất phát từ đỉnh đó. Nếu có ~n~ đỉnh thì ta chỉ cần dùng ~n~ số nguyên. Ở đây ta chỉ xét các đồ thị đơn, giữa ~2~ đỉnh không có quá một cạnh và không có cạnh nối một đỉnh với chính nó.
Ví dụ, đồ thị ở hình bên có ~4~ đỉnh và có thể được mô tả bởi dãy ~4~ số nguyên ~3, 3, 3, 3~.
Yêu cầu:
Cho ~n~ số nguyên ~(1 < n ≤ 10000)~. Hãy xác định có tồn tại hay không một đồ thị nhận các số đã cho làm bậc của đỉnh.
Input
Dòng đầu là số ~T~ là số bộ dữ liệu (~T <= 10~) Tiếp theo là ~T~ dòng, mỗi dòng là một bộ dữ liệu, số đầu tiên trên dòng là ~n~, tiếp theo là ~n~ số nguyên mô tả bậc của các đỉnh.
Output
Gồm ~T~ dòng, mỗi dòng ứng với một bộ dữ liệu một câu trả lời: ~YES~ (tồn tại đồ thị) hoặc ~NO~ (không tồn tại đồ thị).
Sample Input
3
4 3 3 3 3
6 2 4 5 5 2 1
5 3 2 3 2 1
Sample Output
YES
NO
NO
Nguồn: Trại đông Bảo Lộc 2021 - Thầy Đỗ Đức Đông
Bình luận