Даларан — летающий город магии. Он состоит из $$$n$$$ парящих островов, соединенных $$$m$$$ мостами (каждый мост можно пересечь в обоих направлениях). По этим мостам можно добраться до каждого острова. Было бы обидно, если бы какой-нибудь магический эксперимент пошел ужасно неправильно и этот великолепный город был бы разрушен, верно?

Ну, теперь угадайте, что случилось. На острове $$$1$$$ был открыт портал в мир демонов. Сейчас начало $$$1$$$-го дня катастрофы, и все $$$k$$$ магов собрались на острове $$$1$$$ (они пытались закрыть портал, но поняли, что это невозможно). В начале $$$2$$$-го дня гигантская орда демонов выйдет из портала, захватит остров $$$1$$$ и убьет каждого мага, оставшегося на этом острове. В течение каждого дня $$$i$$$, если остров $$$v$$$ был захвачен демонами к началу дня, орда демонов будет путешествовать по всем таким мостам, одним из концов которых является $$$v$$$, захватывать каждый остров, который они достигнут, и убивать каждого мага, которого они встретят на своем пути.

Каждый мост содержит ровно один волшебный камень. Каждый маг в начале дня может выполнить одно из следующих действий:

• потратить один день для пересечения одного из мостов, соединенных с островом, где в настоящее время находится маг. Проходя через мост, маг может забрать с него магический камень (если таковой имеется; каждый магический камень может быть поднят не более чем одним магом). Если мост будет пройден демонами в тот же день, или к началу следующего дня тот остров, на который отправляется маг, будет уже захвачен демонической ордой (даже если они прибудут туда в тот же момент), и маг будет убит.
• выполнить ритуал телепортации, чтобы добраться до безопасного места за пределами Даларана. Этот ритуал потребляет два магических камня (и не может быть выполнен, если у мага меньше двух камней).

Каждый магический камень распадается за $$$2$$$ дня — если его поднять в середине дня $$$i$$$, он распадается в середине дня $$$i + 2$$$. Если камень распался, то его нельзя использовать в ритуале телепортации.

Посчитайте максимальное количество магов, которые смогут добраться до безопасного места.