P4 Decomposition - Repovive Standard Round 4 | Repovive

11F. P4 Decomposition

3000 pts1s256 MB

You are given a complete graph with $n$ vertices, numbered from $1$ to $n$ .

A $P4$ is a simple path with $4$ distinct vertices and $3$ edges. For example, the path $a-b-c-d$ uses the edges $(a,b)$ , $(b,c)$ , and $(c,d)$ .

Determine whether it is possible to divide all edges of the complete graph into some $P4$ paths, so that every edge belongs to exactly one path.

If it is possible, output one valid division. Using zero paths is allowed.

Constraints

$1 \le t \le 50$
$1 \le n \le 500$

Input

t

\left. \begin{array}{l} n \end{array} \right\} \times t

Output

For each test case, first print Yes if it is possible, or No otherwise.

If it is possible, print an integer $k$ on the next line, the number of paths.

Then print $k$ lines. Each line must contain four distinct integers $a$ , $b$ , $c$ , and $d$ , denoting the path $a-b-c-d$ . If $k=0$ , print no path lines.

Every edge of the complete graph must appear in exactly one printed path.

Samples

Input

Case 1

Case 2

Case 3

Case 4

Case 5

Explanation

Case 1

For $n=1$ , there are no edges, so zero paths are enough.

Case 2

For $n=2$ , the graph has only one edge, so it cannot be divided into paths with three edges.

Case 3

For $n=3$ , it is impossible since a $P4$ needs four distinct vertices.

Case 4

For $n=4$ , the two printed paths use all six edges exactly once.

Case 5

For $n=6$ , the five printed paths use all fifteen edges exactly once.

Output

Case 1

Yes
0

Case 2

No

Case 3

No

Case 4

Case 5

You are given a complete graph with $n$ vertices, numbered from $1$ to $n$ .

A $P4$ is a simple path with $4$ distinct vertices and $3$ edges. For example, the path $a-b-c-d$ uses the edges $(a,b)$ , $(b,c)$ , and $(c,d)$ .

Determine whether it is possible to divide all edges of the complete graph into some $P4$ paths, so that every edge belongs to exactly one path.

If it is possible, output one valid division. Using zero paths is allowed.

$1 \le t \le 50$
$1 \le n \le 500$

t

\left. \begin{array}{l} n \end{array} \right\} \times t

For each test case, first print Yes if it is possible, or No otherwise.

If it is possible, print an integer $k$ on the next line, the number of paths.

Then print $k$ lines. Each line must contain four distinct integers $a$ , $b$ , $c$ , and $d$ , denoting the path $a-b-c-d$ . If $k=0$ , print no path lines.

Every edge of the complete graph must appear in exactly one printed path.

For $n=1$ , there are no edges, so zero paths are enough.

For $n=2$ , the graph has only one edge, so it cannot be divided into paths with three edges.

For $n=3$ , it is impossible since a $P4$ needs four distinct vertices.

For $n=4$ , the two printed paths use all six edges exactly once.

For $n=6$ , the five printed paths use all fifteen edges exactly once.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

11F. P4 Decomposition

Constraints

Input

Output

Samples

11F. P4 Decomposition

Constraints

Input

Output

Samples