P7010 [CERC2013] Subway

Johny is going to visit his friend Michelle. His dad allowed him to go there on his own by subway. Johny loves traveling by subway and would gladly use this opportunity to spend half a day underground, but his dad obliged him to make as few line changes as possible. There are a lot of stations in the city, and several subway lines connecting them. All trains are perfectly synchronized $-$ the travel between two consecutive stations on every line takes exactly one minute, and changing lines at any station takes no time at all. Given the subway map, help Johny to plan his trip so that he can travel for as long as possible, while still following his dad's order.

N/A

N/A

Time limit: 8 s, Memory limit: 128 MB.