Problem Description

Given three positive integers $n, d, k$, you need to construct a rooted tree with root node $1$ such that:

• The tree has $n$ nodes.
• The sum of distances from every node to the root is $d$.
• For every node that is not a leaf, the number of its direct children is at least $k$.
• Among all valid trees, the maximum depth of all nodes is as small as possible.

Notes:

• Distance: the number of edges on the simple path between two nodes.
• Leaf node: a non-root node that has no children.
• The depth of the root is $0$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.
For each test case, there is one line with three positive integers $n, d, k$, with the meaning as described above.

Output Format

For each test case:

• If a solution exists, output YES on the first line, then output $n-1$ positive integers on the next line. The $i$-th integer $a_i$ means that $a_i$ is the parent of node $i+1$, and $a_i \le i$.
• If no solution exists, output NO.

If there are multiple valid answers, you may output any one of them.

In particular, if $n=1$ and a solution exists, output an empty line for the construction.

3
5 4 1
5 6 1
5 7 1

YES
1 1 1 1
YES
1 1 3 3
YES
1 2 2 2

3
5 4 2
5 6 2
5 7 2

YES
1 1 1 1
YES
1 1 3 3
NO

Hint

Sample Explanation

For the second query of the second sample, $n=5, d=6, k=2$. That is, you need to construct a tree with $5$ nodes, where the sum of distances from all nodes to node $1$ is $6$, and every non-leaf node has at least $k$ child nodes.

The following is the tree constructed in the sample:

The distances from nodes $1,2,3,4,5$ to the root node $1$ are $0,1,1,2,2$, respectively, and their sum is $6$, which satisfies the condition. Also, the non-leaf nodes $1$ and $3$ both have at least $2$ children. It can be proven that among all valid constructions, this one has the minimum possible maximum depth, which is $2$ here.

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that: $1 \le n \le 10^5$, $1 \le T \le 10^5$, $1 \le k \le 10^5$, $\sum n \le 10^6$, $1 \le d \le 10^{10}$.

Translated by ChatGPT 5