G. Portal 2
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
So I run to the river

It was boilin', I run to the sea

It was boilin', I run to the sea

It was boilin', all on that day

— Nina Simone, Sinnerman

$$$~\\$$$

Once again, Vistar finds himself trapped in a mysterious maze consisting of $$$n$$$ rooms. Surprisingly, the maze has no traditional doors — Instead, the $$$i-$$$th room contains $$$a_i$$$ portals.

Each portal is uniquely paired with exactly one other portal in the maze, forming a bidirectional connection. When Vistar enters a portal, he is instantly transported to the room of its paired portal. In particular, the portal cannot be paired to another portal within the same room.

Vistar begins his journey in room $$$1$$$ and aims to reach room $$$n$$$. However, the specific pairings of the portals are unknown. Your task is to determine whether Vistar can always reach the exit, regardless of how the portals are paired.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T \le 5\cdot 10^4)$$$ — the number of test cases. For each test case:

The first line of input contains one integer $$$n$$$ $$$(2 \le n\le 10^5)$$$. The second line contains an array $$$a$$$ of length $$$n$$$ $$$(1 \le a_i\le 5000, \sum_{i=1}^{n}a_i$$$ is even$$$)$$$.

It is guaranteed that:

  • The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
  • At least one valid portal pairing exists for each test case.
Output

For each test case, output "Yes" if Vistar can always reach room $$$n$$$ or "No" if not.

You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", and "YES" will be recognized as a positive response).

Example
Input
3
3
2 2 2
4
1 2 2 1
5
3 2 1 4 4
Output
Yes
Yes
No
Note

For sample $$$3$$$, a possible pairing is shown below:

It can be proven that for samples $$$1$$$ and $$$2$$$, Vistar can always reach room $$$n$$$ regardless of how the portals are paired.