5612: Problem F. Fixing Networks
[Creator : ]
Description
After the last network breakdown, you've been assigned to redesign the signal transmission network of ICPC (Internet Clogging Prevention Corporation)!
There are $n$ signal stations in total, they are all newly built and can establish bidirectional signal connections with at most $d$ other stations. ICPC demands you to reach the full potential of the network with these fancy stations. That is, all stations should have exactly $d$ connections, no connection with oneself, and no multiple connections between the same pair of stations.
These stations will later be assigned to $c$ departments of ICPC. Each department wants at least one station, and all stations will be assigned to these departments. To prevent another network breakdown, all stations assigned to the same department should be able to communicate with each other, while stations assigned to different departments should not be able to do so. Two stations can communicate with each other when there is a sequence of stations that begins and ends at these two stations, and every adjacent station in the sequence has a direct signal connection.
Assigning stations to departments is not your job; However, since you are probably the only responsible person left in ICPC, you want to make sure it is at least possible. Give a network proposal that satisfies all the restrictions above, or determine it is impossible.
There are $n$ signal stations in total, they are all newly built and can establish bidirectional signal connections with at most $d$ other stations. ICPC demands you to reach the full potential of the network with these fancy stations. That is, all stations should have exactly $d$ connections, no connection with oneself, and no multiple connections between the same pair of stations.
These stations will later be assigned to $c$ departments of ICPC. Each department wants at least one station, and all stations will be assigned to these departments. To prevent another network breakdown, all stations assigned to the same department should be able to communicate with each other, while stations assigned to different departments should not be able to do so. Two stations can communicate with each other when there is a sequence of stations that begins and ends at these two stations, and every adjacent station in the sequence has a direct signal connection.
Assigning stations to departments is not your job; However, since you are probably the only responsible person left in ICPC, you want to make sure it is at least possible. Give a network proposal that satisfies all the restrictions above, or determine it is impossible.
Input
The only line of the input contains three integers $n,d$ and $c$ ($1 \leq c \leq n \leq 100\,000$, $0 \leq d < n$, $n\times d \leq 200\,000$), denoting the number of signal stations, the number of connections each station can establish, and the number of departments.
Output
If it is impossible to connect the stations in such a way, print a single line containing $''{No}''$. Otherwise, print $''{Yes}''$ in the first line, then print $n$ lines, with the $i$-th line containing $d$ numbers, denoting the $d$ stations that have connections with the $i$-th station. $\textbf{The $d$ numbers should be sorted in ascending order.}$
The label of all stations should be integers in the range $[1,n]$. If there is more than one solution, any one of them will be accepted.
Sample 1 Input
12 3 2
Sample 1 Output
Yes
2 5 8
1 3 6
2 4 7
3 5 8
1 4 6
2 5 7
3 6 8
1 4 7
10 11 12
9 11 12
9 10 12
9 10 11
Sample 2 Input
3 2 2
Sample 2 Output
No