В городе живет N мегамозгов. Город терроризируют оккупанты. Поскольку почта и телефон прослушиваются, мегамозги решили использовать для экстренной связи голубиную почту.

Голубиная почта работает так: два мегамозга обмениваются голубями. Один мегамозг может привязать к лапе полученного голубя записку, и голубь отнесет записку своему настоящему хозяину (то есть именно к тому, от кого он был получен). Голубь от одного мегамозга до другого летит ровно один час. Один мегамозг может выпустить за один раз ровно одного голубя (то есть ровно одного голубя в час).

Итак. Некоторые мегамозги обменялись голубями. Обменялись далеко не каждый с каждым, но достаточно для того, чтобы записку можно было переслать между любыми двумя мегамозгами (возможно, больше чем в один перелет). Все мегамозги знают, кто с кем обменялся голубями.

В какой-то момент у одного мегамозга появляется важная для жизни информация, которую необходимо срочно передать нескольким другим мегамозгам. Например, одному мегамозгу становится известно, что оккупанты хотят убить всех мегамозгов, у которых светлые волосы и голубые глаза, и он хочет предупредить своих собратьев с такой внешностью, чтобы они немедленно спрятались. Поскольку все мегамозги знают друг друга, каждый получивший эту информацию однозначно понимает, кому она предназначается. И поскольку все телефоны прослушиваются, воспользоваться можно только голубиной почтой. Информация копируется, то есть мегамозг раз в час может высылать очередного голубя с сообщением. Важная информация появляется уже после того, как мегамозги обменялись голубями (то есть учитывать, откуда и куда должна быть передана информация, при обмене голубями не получится).

Вопрос: как должны действовать мегамозги, чтобы предупредить собратьев как можно быстрее (при этом потратив наименьшее количество голубей)?

Второй вопрос: как должны действовать мегамозги, если известно, что оккупанты охотятся на голубей, и любого голубя могут сбить?