ШЮП Ноябрьск: Графы Мосты, точки сочленения и компоненты сильной связности

В некотором царстве жил-был король. У него была дочка – принцесса невиданной красоты. И настала пора её замуж отдать. В богатом королевстве неподалеку жил принц. И собрался король отвести принцессу, да не знает, какой маршрут выбрать. На тех землях ещё издревле было множество дорог – горизонтальных и вертикальных, и образовывали они клетчатую сетку на земле той. На перекрёстках располагались города. Город принцессы имеет координаты \((0, 0)\), а принца – \((n, m)\), уравнения дорог имеют вид \(x = x_0\) или \(y = y_0\), где \(x_0\), \(y_0\) целые. Король хочет проехать по как можно меньшему числу дорог, потому что он грабителей боится да вернуться хочет поскорей. Вам, как придворному математику, нужно посчитать, сколькими способами это можно сделать.

7 7

3432

4 1

5