歹丸國的新總統正在重新擘畫歹丸國的城市規劃，其中最重要的問題就是城市間的交通。歹丸國的城市之間以有向道路相連，此外因為歹丸國奇特的地理環境，城市間的有向道路長度也十分不一。新總統決定要以「慘字度」來評估一個道路規劃的好壞。「慘字度」的定義如下：$\displaystyle\max_{\forall i \neq j} \text{mindist}(i,j)$ ，其中 $\text{mindist}(i,j)$ 代表從城市 $i$ 到城市 $j$ 的最短距離。從定義我們可以知道「慘字度」越大的道路規劃越糟糕。如果在某個道路規劃下有一個城市無法到達另一個城市，我們稱這個規劃為「大慘字規劃」。

現在新總統決定要在歹丸國建立 $N$ 個城市，他在他的城市規劃藍圖上依序（從編號 $1$ 到編號 $N$ ）加入城市。每加入一個新的城市，他會決定這個新的城市要與先前建立的哪些城市之間蓋有向道路，以及這些道路的長度。身為他的助理，總統希望你在他加入每個新的城市後，告訴他目前道路規劃的「慘字度」。