Tree Desompisition - Repovive Premier Round 2 | Repovive

3G. Tree Desompisition

3000 pts2s256 MB

You are given two integers $n$ and $d$ , where $n$ is even. Consider the complete graph $K_n$ on vertices $1,2,\dots,n$ .

You must partition all edges of $K_n$ into exactly $\frac{n}{2}$ spanning trees such that in each spanning tree, the degree of every vertex is either $1$ or $d$ .

If it is impossible, print No. Otherwise, print Yes and output the partition in the format described below.

Constraints

$1 \le t \le 50$
$3 \le n \le 100$
$n$ is even
$2 \le d \le n-1$

Input

t \\[0.5em] \left. \begin{array}{l} n \quad d \end{array} \right\} \times t

Output

For each test case, output either:

\texttt{No}

or:

\texttt{Yes} \\[0.5em] \left. \begin{array}{l} a_{2,1} \\ a_{3,1}\ \ a_{3,2} \\ \vdots \\ a_{n,1}\ \ a_{n,2}\ \ \cdots\ \ a_{n,n-1} \end{array} \right.

where $a_{i,j}$ (for $1 \le j < i \le n$ ) is the index of the spanning tree that contains the edge $(i,j)$ , and it must satisfy: $1 \le a_{i,j} \le \frac{n}{2}$ .

Samples

Input

Case 1

6 2

Case 2

6 3

Case 3

8 3

Explanation

Case 1

The output labels all edges into $\frac{n}{2}=3$ spanning trees, and in each tree every vertex has degree $1$ or $2$ .

Case 2

The output labels all edges into $\frac{n}{2}=3$ spanning trees, and in each tree every vertex has degree $1$ or $3$ .

Case 3

It is impossible.

Output

Case 1

Case 2

Case 3

No

You are given two integers $n$ and $d$ , where $n$ is even. Consider the complete graph $K_n$ on vertices $1,2,\dots,n$ .

You must partition all edges of $K_n$ into exactly $\frac{n}{2}$ spanning trees such that in each spanning tree, the degree of every vertex is either $1$ or $d$ .

If it is impossible, print No. Otherwise, print Yes and output the partition in the format described below.

Constraints

$1 \le t \le 50$
$3 \le n \le 100$
$n$ is even
$2 \le d \le n-1$

t \\[0.5em] \left. \begin{array}{l} n \quad d \end{array} \right\} \times t

For each test case, output either:

\texttt{No}

or:

\texttt{Yes} \\[0.5em] \left. \begin{array}{l} a_{2,1} \\ a_{3,1}\ \ a_{3,2} \\ \vdots \\ a_{n,1}\ \ a_{n,2}\ \ \cdots\ \ a_{n,n-1} \end{array} \right.

where $a_{i,j}$ (for $1 \le j < i \le n$ ) is the index of the spanning tree that contains the edge $(i,j)$ , and it must satisfy: $1 \le a_{i,j} \le \frac{n}{2}$ .

The output labels all edges into $\frac{n}{2}=3$ spanning trees, and in each tree every vertex has degree $1$ or $2$ .

The output labels all edges into $\frac{n}{2}=3$ spanning trees, and in each tree every vertex has degree $1$ or $3$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

3G. Tree Desompisition

Input

Output

Samples

3G. Tree Desompisition

Constraints

Input

Output

Samples

Constraints