Phép Xor

View as PDF

Submit solution

Points: 1.05 (partial)
Time limit: 0.25s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~1~ tập ~N~ số nguyên dương ~A_{1}~, ...~A_{N}~. Tập số này được gọi là phụ thuộc tuyến tính nếu tồn tại ~1~ số nguyên ~A_{i}~ nào đó thoả mãn:

~A_{i} = A_{j_1}~ ~\oplus~ ~A_{j_2}~ ...~\oplus~ ~A_{j_k}~ (với ~i~, ~j_1~, ~j_2~, ..., ~j_k~ đôi một khác nhau và ~k~ là ~1~ số tuỳ ý). Nếu tập số này không phụ thuộc tuyến tính thì được gọi là độc lập tuyến tính.

Hãy kiểm tra tập ~N~ số nguyên dương ~A_{1}~ ...~A_{N}~ có phải là độc lập tuyến tính hay không? Nếu không hãy chỉ ra phải loại đi ít nhất bao nhiêu phần tử để tập còn lại là ~1~ tập độc lập tuyến tính.

Input

Dòng ~1~: số nguyên dương ~T~ là số bộ test.

Tiếp theo là ~T~ bộ test, mỗi bộ test có format như sau:

Dòng ~1~: số ~N~ ~(1 \leq N \leq 10000)~.

Dòng ~2~: ~N~ số nguyên dương ~A_{1}, \dots, A_{N}~. ~(1 \leq A_{i} \leq 2 \cdot 10^9)~.

Output

Với mỗi test, nếu tập ~N~ số là độc lập tuyến tính thì ghi ra "YES" ngược lại ghi ra "NO X" với ~X~ là số số ít nhất cần phải bỏ đi để tập còn lại trở thành độc lập tuyến tính.

Sample Input

2
2
1 2
3
1 2 3

Sample Output

YES
NO 1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.