問題文

Atcoder運送会社には、N個の工場が存在します。

217X年、この会社では、1つだけ困っていることがあります。これは、会社と会社を結ぶ道が存在しないことです。

運送会社社長「これは大問題だ!!すぐにでも直さないとやばいぞ!!」

よって、今すぐ計画を立てることになりました。

この会社は、運送関連のことをやっているため、製品を地方から都市、都市から地方へ迅速に運ばなければなりません。そのため、会社専用の道を作ると多くの注文にも対応できます。

ただし、以下のような条件で道を作る必要があります。

• できるだけ運送トラックの制限速度を上げるために、道路は直線にする必要があります。
• 立体交差をすると大幅に費用が増えるので、道と道は工場以外で交差してはいけません。
• そのように全ての専用道路の制限速度を速くした上で、できるだけ目的の会社に速く速く運びたいので、 できるだけ道をつくります。
• 道は工場と工場の間をつなぐものとします。

ただ、会社は最適解を導き出す方法がわかりませんでした。

そこで、優秀なプログラマーであるあなたに、最適解を探してくれと会社から頼まれました。最大で道が何本建てられるか求めてください。

ただし、問題文中の条件は厳守するものとします。

注意:問題文中の217X年は、時空を超えた世界での時間とします。ここでの時間は今現在とみなしてよいでしょう。