Mary and Tom are taking a road trip from New York City to San Francisco. Because it is a 44-hour drive, Mary and Tom decide to switch o driving at each rest stop they visit. However, because Mary has a better sense of direction than Tom, she should be driving both when they depart and when they arrive (to navigate the city streets). Given a route map represented as a weighted directed graph G = (V;E) with positive edge lengths (the length of edge e is `e > 0), where vertices represent rest stops and edges represent routes between rest stops, devise an ecient algorithm to nd a route (if possible) of minimum distance between New York City and San Francisco such that Mary and Tom alternate edges and Mary drives the rst and last edge.