AtCoder Beginner Contest 131：E - Friendships
問題
解法
完全グラフにおいては最短距離が 2 であるような頂点の組み合わせは 0 通りになる．ここから辺を 1 本ずつ取っていくと，この頂点の組み合わせは 1 つずつ増えていく．よって，まず最初に完全グラフを作り，その後 K 本だけ，グラフが連結を保つように，辺を取り除いていけばよい．O(N^2)．
解答
完全グラフは当然だけれども各頂点間の距離が 1 なので，これを用いればあとは非常に簡単だと感じた．
完全グラフにおいては最短距離が 2 であるような頂点の組み合わせは 0 通りになる．ここから辺を 1 本ずつ取っていくと，この頂点の組み合わせは 1 つずつ増えていく．よって，まず最初に完全グラフを作り，その後 K 本だけ，グラフが連結を保つように，辺を取り除いていけばよい．O(N^2)．
完全グラフは当然だけれども各頂点間の距離が 1 なので，これを用いればあとは非常に簡単だと感じた．