Автобусні маршрути

У новому передмісті Миколаєва, що має форму прямокутника, усі дороги йдуть або строго з півдня на північ, або строго із заходу на схід. Таким чином, кожні дві дороги або паралельні одна до одної, або перпендикулярні й перетинаються в одному з перехресть. Усього в передмісті є $N$ горизонтальних доріг, $M$ вертикальних доріг та, відповідно, N \cdot M перехресть.

Для передмістя саме зараз розробляють схему автобусних маршрутів. Усі маршрути повинні починатися у перехресті, що розташоване в лівому нижньому куті мапи, а закінчуватися у перехресті в її правому верхньому куті. До того ж між початковою та кінцевою точкою автобус повинен їхати за найкоротшим маршрутом, тобто завжди на північ або на схід (на будь-якому перехресті на своєму шляху, однак, автобус може змінити напрям свого руху з північного на східний чи навпаки). Деякі перехрестя можуть бути важливими: вони розташовані поблизу густонаселених районів, і через них неодмінно слід пропустити принаймні один автобусний маршрут.

Ваша задача — спланувати мережу маршрутів таким чином, щоб через кожне важливе перехрестя проходив принаймні один маршрут, але загальна кількість маршрутів вийшла при цьому якомога меншою.