Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMDEGREE - Pirate đãng trí

Những cây cầu dừa nối những hòn đảo của Pirate đang gây trở ngại lớn cho anh ấy khi việc kinh doanh ngày càng mở rộng. Một ngày nọ, Pirate quyết định thiết kế một hệ thống đường mới nối các hòn đảo với nhau. Mỗi đường nối sẽ rộng hơn trước và cho phép di chuyển theo hai chiều. Để tiết kiệm chi phí, giữa hai hòn đảo chỉ nên có một đường nối trực tiếp. Bản vẽ đã xong hoàn thành, giờ chỉ còn việc bắt tay vào xây dựng. Tuy nhiên, do tính đãng trí kinh niên của mình, Pirate đã làm mất bản vẽ thiết kế. Lục tung đống giấy tờ thì chỉ còn lại một mảnh giấy thống kê về số hòn đảo (khác) có đường nối trực tiếp đối với từng hòn đảo.

Việc nâng cấp không thể chậm trễ được, Pirate cần phải bắt tay vào vẽ lại bảng thiết kế dựa vào bảng thống kê trên. Nhưng khổ một nỗi, anh vẫn đang nghi ngờ tính chính xác của bảng thống kê này. Vì thế, trước hết, các bạn hãy giúp Pirate xác định xem có tồn tại một hệ thống đường thỏa mãn bảng thống kê tìm được không.

Input

-   Dòng thứ nhất ghi một số nguyên T – số bộ test.

-   Tiếp theo là T test, mỗi test được mô tả như sau:

    + Dòng đàu tiên ghi một số nguyên N – số lượng các hòn đảo.

    + N dòng tiếp theo: mô tả bảng thống kê. 

Output

-   Gồm T dòng, mỗi dòng ghi “YES” nếu có tồn tại một hệ thống đường thỏa mãn bảng thống kê trong test tương ứng, hoặc “NO” nếu ngược lại. 

Giới hạn

  • 1 ≤ T ≤ 10.
  • 1 ≤ N ≤ 105.
  • 60% bộ test có 1 ≤ N ≤ 103.
  • Mỗi số trong input là một số nguyên không âm không quá 109.

Example

Input:
1
4
2
2
1
1
Output:
YES

Giải thích: Có 4 hòn đảo, số lượng đường nối trực tiếp với từng hòn đảo lần lượt là 2, 2, 1, 1. Ta có thể xây dựng được một hệ thống đường như hình vẽ.


Được gửi lên bởi:VOJ Team
Ngày:2011-07-22
Thời gian chạy:1.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC GAWK MAWK BC C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PROLOG PY_NBC R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Nguồn bài:VNOI Marathon 2011 - Tác giả: Nguyễn Xuân Khánh

hide comments
2012-09-16 08:47:18 Shinken Yellow
Chat nhi phan O(NlogN)---70???
2011-07-28 07:52:24 St.VDQD
bài này mình sort+O(n) AC

Last edit: 2011-07-28 07:55:03
2011-07-28 05:41:11 TungNH
time 6s ma


Last edit: 2011-07-28 05:41:40
2011-07-26 15:45:09 thphong
nlog(n) AC, chắc bị sai test nào rồi
2011-07-25 09:22:02 PSA.X.A.N.A
bai` nay` O(nlogn) dc co' 70, ko b' la` WA hay TLE nua
2011-07-24 15:29:21 pham tuan minh
hinh nhu la cap ghep


Last edit: 2011-07-24 15:29:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.