Даларан — летающий город магии. Он состоит из \(n\) парящих островов, соединенных \(m\) мостами (каждый мост можно пересечь в обоих направлениях). По этим мостам можно добраться до каждого острова. Было бы обидно, если бы какой-нибудь магический эксперимент пошел ужасно неправильно и этот великолепный город был бы разрушен, верно?
Ну, теперь угадайте, что случилось. На острове \(1\) был открыт портал в мир демонов. Сейчас начало \(1\)-го дня катастрофы, и все \(k\) магов собрались на острове \(1\) (они пытались закрыть портал, но поняли, что это невозможно). В начале \(2\)-го дня гигантская орда демонов выйдет из портала, захватит остров \(1\) и убьет каждого мага, оставшегося на этом острове. В течение каждого дня \(i\), если остров \(v\) был захвачен демонами к началу дня, орда демонов будет путешествовать по всем таким мостам, одним из концов которых является \(v\), захватывать каждый остров, который они достигнут, и убивать каждого мага, которого они встретят на своем пути.
Каждый мост содержит ровно один волшебный камень. Каждый маг в начале дня может выполнить одно из следующих действий:
- потратить один день для пересечения одного из мостов, соединенных с островом, где в настоящее время находится маг. Проходя через мост, маг может забрать с него магический камень (если таковой имеется; каждый магический камень может быть поднят не более чем одним магом). Если мост будет пройден демонами в тот же день, или к началу следующего дня тот остров, на который отправляется маг, будет уже захвачен демонической ордой (даже если они прибудут туда в тот же момент), и маг будет убит.
- выполнить ритуал телепортации, чтобы добраться до безопасного места за пределами Даларана. Этот ритуал потребляет два магических камня (и не может быть выполнен, если у мага меньше двух камней).
Каждый магический камень распадается за \(2\) дня — если его поднять в середине дня \(i\), он распадается в середине дня \(i + 2\). Если камень распался, то его нельзя использовать в ритуале телепортации.
Посчитайте максимальное количество магов, которые смогут добраться до безопасного места.