The Night Round

A night guard has to check every room of a building. The rooms are numbered 0 to n - 1, and graph[i] lists the rooms joined to room i by a door. Doors work both ways, and every room can be reached from every other room. The guard may start in any room, finish in any room and pass through rooms as many times as needed. Walking through one door is one step.

Write shortest_walk(graph) that returns the fewest steps that visit every room at least once.

Examples

shortest_walk([[1, 2, 3], [0], [0], [0]])  # returns 4
shortest_walk([[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]])  # returns 4
shortest_walk([[]])  # returns 0

In the first building, room 0 is a hall with three rooms off it. Starting in room 1, the guard walks to the hall, into room 2, back to the hall and into room 3: 4 steps. In the second, the walk 0, 1, 4, 2, 3 takes 4 steps.

Constraints

• 1 <= n <= 12, and graph[i] never contains i.
• If room j is in graph[i], then room i is in graph[j].