I got this question in google interview and completely blanked out. Can someone try to solve this question and share your approach? Thanks

There's a country with multiple cities. Each city has 3 letter name. We ae given pair of cities connected by road. Friend provides itinerary of their travel as AAA-BBB-CCC-DDD in that order. You determine that itinerary is impossible as there's no road between BBB and CCC and city DDD doesn't exist. We relaise with changes in input/given itinerary we can create a valid itinerary like AAA-BBX-CCC-DDY. This new valid itinerary has 2 letter change then the itinerary shared by friend. You are given 2 functions implemented that gives list of city names and another function which gives neighbours of city. Given an invalid itinerary you need to find a valid itinerary which has minimum character changes to given itinerary.