小奇和魔法猪打开了战狂的遗迹，穿越到了东元20年。东元元年，战狂率领一千万士兵毁灭了一个又一个文明，并建立起了新文明——昌和帝国，招募了八位伟人：大将军、海军上将、大科学家、大预言家、大工程师、大艺术家、大音乐家、大作家。东元15年，伟大的革命领袖方方方召集仅存的几个文明，组成联盟对抗战狂。方方方设计先后杀死了大作家和大艺术家，并重创了战狂。东元20年，方方方率军进攻大将军，大将军花重金（1600奥术之尘）请来了砰砰博士，炸死了方方方。随后，大将军占领了联盟数座城市并包围了联盟首都。这时，小奇和魔法猪从天而降。它们听说了方方方的英勇事迹，十分感动，决定帮助联盟对抗战狂。在接下来一个月的时间里，小奇和魔法猪夺回了n-1座城市。为了纪念方方方，小奇把联盟改名为魔方国，并打算修建m条道路。一条道路必须要连接两个不同的城市（首都也算城市），两个城市之间可以有多条道路。在修建完道路后，小奇会在一些城市中放置魔法守卫。一个魔法守卫会守护它所在的城市以及与从它所在的城市出发，经过不超过k条边所能到达的城市。在守护所有城市的基础上，小奇会使魔法守卫的数量尽可能少。显然，每一种修建道路的方案都会对应一个最少守卫数。现在，小奇想知道最少守卫数可能是多少
