Counting the ways of Making Friends is Fun

条件による縛りもあり，$N-1$ 回の操作後にできる友人関係をグラフで表してみると，木となっています。
このことから，この問題は，$N$ 個のラベルが付いた頂点を持つ木の個数を数え上げる問題であることが分かります。
よって，答えはケイリーの公式より，$N^{N-2}$ です。