九条可怜是一个热爱阅读的女孩子。
这段时间，她看了一本非常有趣的小说，这本小说的架空世界引起了她的兴趣。
这个世界有n个城市，这n个城市被恰好n?1条双向道路联通，即任意两个城市都可以互相到达。同时城市1坐落在世
界的中心，占领了这个城市就称霸了这个世界。
在最开始，这n个城市都不在任何国家的控制之下，但是随着社会的发展，一些城市会崛起形成国家并夺取世界的
霸权。为了方便，我们标记第i个城市崛起产生的国家为第i个国家。在第i个城市崛起的过程中，第i个国家会取得
城市i到城市1路径上所有城市的控制权。
新的城市的崛起往往意味着战争与死亡，若第i个国家在崛起中，需要取得一个原本被国家j(j!=i)控制的城市的控
制权，那么国家i就必须向国家j宣战并进行战争。
现在，可怜知道了，在历史上，第i个城市一共崛起了ai次。但是这些事件发生的相对顺序已经无从考究了，唯一
的信息是，在一个城市崛起称霸世界之前，新的城市是不会崛起的。战争对人民来说是灾难性的。可怜定义一次崛
起的灾难度为崛起的过程中会和多少不同的国家进行战争（和同一个国家进行多次战争只会被计入一次）。可怜想
要知道，在所有可能的崛起顺序中，灾难度之和最大是多少。
同时，在考古学家的努力下，越来越多的历史资料被发掘了出来，根据这些新的资料，可怜会对ai进行一些修正。
具体来说，可怜会对ai进行一些操作，每次会将ax加上w。她希望在每次修改之后，都能计算得到最大的灾难度。
然而可怜对复杂的计算并不感兴趣，因此她想让你来帮她计算一下这些数值。
对题面的一些补充：
1:同一个城市多次崛起形成的国家是同一个国家，这意味着同一个城市连续崛起两次是不会和任何国家开战的：因
为这些城市原来就在它的控制之下。
2:在历史的演变过程中，第i个国家可能会有一段时间没有任何城市的控制权。但是这并不意味着第i个国家灭亡了
，在城市i崛起的时候，第i个国家仍然会取得1到i路径上的城市的控制权
BZPRO