One Cycle Each - Repovive Standard Round 6 | Repovive

18C. One Cycle Each

1500 pts2s256 MB

You are given a sequence $a_1,a_2,\ldots,a_n$ .

Determine whether there exists an undirected multigraph with vertices numbered from $1$ to $n$ such that:

the degree of vertex $i$ is exactly $a_i$ ;
every vertex belongs to exactly one cycle.

The graph does not have to be connected. Loops and multiple edges are allowed.

A loop is considered a cycle of length $1$ , and it contributes $2$ to the degree of its endpoint. Every pair of parallel edges forms a cycle of length $2$ . Cycles that use different edges are considered different.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$2 \le a_i \le n$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

For each test case, output Yes if such a multigraph exists, and No otherwise.

The answer is case-insensitive. For example, YES, yes, and yEs are all accepted.

\left. \begin{array}{l} \texttt{Yes or No} \end{array} \right\} \times t

Samples

Input

Case 1

3
2 2 2

Case 2

4
3 3 2 2

Case 3

4
3 2 2 2

Explanation

Case 1

Place one loop on each of the $3$ vertices and add no other edges. Every degree is $2$ , and each vertex belongs only to its own loop.

Case 2

Place one loop on every vertex, then add one edge between vertices $1$ and $2$ . Their degrees become $3$ , the other two degrees remain $2$ , and the added edge creates no new cycle.

Case 3

The degree sum is $3+2+2+2=9$ . In every undirected multigraph, loops included, the degree sum is twice the number of edges and is therefore even. Hence, no such graph exists.

Output

Case 1

Yes

Case 2

Yes

Case 3

No

Input

Case 1

8
5 3 3 3 2 2 2 2

Case 2

10
4 4 4 4 2 2 2 2 2 2

Explanation

Case 1

Loops on all vertices and three edges from vertex $1$ to vertices $2$ , $3$ , and $4$ give the required degrees.

Case 2

After reserving degree $2$ for one cycle at each vertex, the first $4$ vertices would need degree sum $8$ in an acyclic graph, which is impossible.

Output

Case 1

Yes

Case 2

No

You are given a sequence $a_1,a_2,\ldots,a_n$ .

Determine whether there exists an undirected multigraph with vertices numbered from $1$ to $n$ such that:

the degree of vertex $i$ is exactly $a_i$ ;
every vertex belongs to exactly one cycle.

The graph does not have to be connected. Loops and multiple edges are allowed.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$2 \le a_i \le n$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

For each test case, output Yes if such a multigraph exists, and No otherwise.

The answer is case-insensitive. For example, YES, yes, and yEs are all accepted.

\left. \begin{array}{l} \texttt{Yes or No} \end{array} \right\} \times t

Place one loop on each of the $3$ vertices and add no other edges. Every degree is $2$ , and each vertex belongs only to its own loop.

Place one loop on every vertex, then add one edge between vertices $1$ and $2$ . Their degrees become $3$ , the other two degrees remain $2$ , and the added edge creates no new cycle.

The degree sum is $3+2+2+2=9$ . In every undirected multigraph, loops included, the degree sum is twice the number of edges and is therefore even. Hence, no such graph exists.

Loops on all vertices and three edges from vertex $1$ to vertices $2$ , $3$ , and $4$ give the required degrees.

After reserving degree $2$ for one cycle at each vertex, the first $4$ vertices would need degree sum $8$ in an acyclic graph, which is impossible.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

18C. One Cycle Each

Constraints

Input

Output

Samples

18C. One Cycle Each

Constraints

Input

Output

Samples