T49882 战争

在2240年，一场巨大的战争在地球联合力量（EAF）与火星联盟(MF)之间展开。至今，双方势均力敌。因最近的一次经济危机，资源紧缺，EAF将被MF勒要更多领土。为此，EAF决定采取战争以来最重要的行动：发动对分散在MF上各处的基地进行同时攻击。EAF的力量大都是mechs——大型两足跛行车，有飞行功能。 典型的MF基地概况如下：构成基地的房屋地跨一到两块领土。每块领土被保护塔产生的穿不透的能量层所笼罩，以免于外来袭击。这些保护塔围绕在领土周围起保护作用。 每座保护塔通过建造在地面上的水道与至少一座塔相联系。当那些相联系的塔围成一圈，它们产生能量层。否则能量层消失。 MF知道如果能量层消失，基地将很容易被EAF的力量侵占，因此，被水道相连的两座塔保护水道免受军事袭击。每座塔有防御功能，能拆卸指定数量的mechs，每个水道在坍塌之前能解决特定数量敌方mechs的袭击。这个数量由水道连接的两塔能拆卸的总数量决定。两座塔不能被一个以上的水道相连。  但是，袭击塔一边的水道不减少塔在另一边能拆卸的mechs的数量。因为这次行动是突袭，所有的对水道的袭击都必须同时，所有水道同时坍塌瓦解。  所有能量层必须废除才算毁灭了一个MF基地。破坏所有水道能达此目的，但也将需要很多mechs 牺牲。EAF只有很少的力量花费了，必须最有效率地部署mechs。 你被赋予这任务，写程序：使EAF胜利。给定一幅保护塔的曲线图，决定哪些水道要被破坏，来使所有能量层消失，要求战斗中牺牲最少的mechs。

第一行为一个整数m，2 < m

一行一个整数，代表EAF摧毁所有能量层所需要消耗的最少数量的mechs。