グラフの詰め込み

あなたは最近、国家グラフ資源委員会が国費で行っているグラフ配布事業に選ばれ、$N$ 頂点の functional graph を手に入れました。functional graph とは、各頂点の出次数がちょうど $1$ である有向グラフのことです。つまり、あなたのグラフの頂点数と辺数は等しくなっています。

しかし、せっかくたくさんの頂点を用意したのに、頂点数と同じ本数の辺しか置かないのは頂点の無駄遣いだというのは、広く知られた常識です。そこで、あなたはこのグラフにもっと辺を詰め込むことにしました。国家グラフ資源委員会も、税金が投じられたグラフの頂点が有効活用されていることを示すため、できるだけ多くの辺を追加すべきだという考えに同意し、あなたにその作業を依頼しました。

ただし、何も制限しなければ、あなたが頂点 $1$ と頂点 $2$ の間に大量の辺を追加して仕事を終えることは、委員会にもお見通しです。そこで、次の制限が設けられました。

• 多重辺を作るような追加はできない。すなわち、頂点 $u$ から頂点 への辺がすでに存在するならば、 から への辺をさらに追加することはできない。