Save the Python Programmers!

Only six teams of Python programmers remain, and they share a network of safe houses. Three teams use CPython and start in houses a, b, and c; the other three teams use Jython and start in houses d, e, and f.

The teams want to swap safe houses: every CPython team must move into the houses that the Jython teams started in, and vice versa. Their guide, Guido, relocates exactly one team each night, moving it from its current house to a nearby house that is directly connected to it. He repeats this night after night until the swap is complete.

Rules:

• Each safe house holds at most one team, so a team may only move into a house that is currently empty.
• Because the two groups distrust each other, Guido must alternate the type of team he moves: a CPython team on one night, a Jython team on the next, then a CPython team again, and so on. On the very first night he may move either type.
• Teams of the same type are interchangeable. The swap is complete as soon as houses d, e, and f are occupied by CPython teams (in any arrangement) and houses a, b, and c are occupied by Jython teams.

There are at most twenty safe houses, each labeled by a single lower-case letter. Determine the minimum number of nights needed to complete the swap, or report that it is impossible.

The input contains one or more scenarios, one per line, and ends at end of file. Each line describes one network of safe houses as space-separated words. Within a word, the first character names a house, and every following character names a house that is directly connected to it, meaning a team can travel between the two in a single night. All connections are bidirectional.

For each scenario, print on its own line the minimum number of nights required to swap the six teams. If the swap can never be completed, print No solution. instead.

Figures 1-3 show example puzzles of increasing difficulty. You can also try one by hand: place one kind of coin on each house that starts with a CPython team and a different kind of coin on each house that starts with a Jython team, then slide them along the connections while obeying the rules above.

Figure 1: a moderately difficult puzzle

Figure 2: a harder puzzle

Figure 3: good luck with this one!