В го­ро­де по­стро­е­но 2019 стан­ций метро. Не­ко­то­рые пары стан­ций со­еди­не­ны тон­не­ля­ми, при­чем от любой стан­ции по тон­не­лям можно до­брать­ся до любой дру­гой. Мэр рас­по­ря­дил­ся ор­га­ни­зо­вать не­сколь­ко линий метро: каж­дая линия долж­на вклю­чать в себя не­сколь­ко раз­лич­ных стан­ций, по­сле­до­ва­тель­но со­еди­нен­ных тон­не­ля­ми (по од­но­му и тому же тон­не­лю может про­хо­дить не­сколь­ко линий). При этом каж­дая стан­ция долж­на ле­жать хотя бы на одной линии. Для эко­но­мии средств сле­ду­ет сде­лать не более k линий. Ока­за­лось, что при­каз мэра не­осу­ще­ствим. При каком наи­боль­шем k это могло про­изой­ти?