Протяженность дорог (в километрах) между населенными пунктами A, B, C, D, E, F, G приведена в таблице.
Отсутствие числа в таблице означает, что дороги между двумя пунктами нет.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | 4 | 5 | 4 | ||||
| B | 4 | 7 | 6 | ||||
| C | 5 | 7 | 4 | 4 | 7 | ||
| D | 4 | 4 | 7 | 3 | |||
| E | 6 | 4 | 5 | ||||
| F | 7 | 3 | |||||
| G | 7 | 3 | 5 | 3 |
Пользуясь информацией, приведенной в таблице, найдите самый длинный путь между населенными пунктами B и G, при условии, что передвигаться можно только по указанным дорогам и посетить нужно каждый населенный пункт, но только 1 раз.