#!/usr/bin/env python3

from collections import deque

class state:
    def __init__(self, left, right):
        self.left = frozenset(left)
        self.right = frozenset(right)

    def accessible(self):
        if 'man' in self.left:
            for x in self.left:
                moving = frozenset(['man', x])
                yield state(self.left - moving, self.right | moving)
        else:
            for x in self.right:
                moving = frozenset(['man', x])
                yield state(self.left | moving, self.right - moving)

    def success(self):
        return not self.left

    def safe(self):
        def tragic(bank):
            BAD = [('cabbage', 'goat'), ('wolf', 'goat')]
            return 'man' not in bank and \
                    any(frozenset(pair) <= bank for pair in BAD)
        return not tragic(self.left) and not tragic(self.right)

    def __str__(self):
        return "left: {}, right: {}".format(
            " & ".join(self.left), " & ".join(self.right)
        )

    def __eq__(self, other):
        return isinstance(other, state) and self.left == other.left

    def __hash__(self):
        return hash(self.left)

def solve():
    init = state(['man', 'cabbage', 'goat', 'wolf'], [])
    Q = deque([init])
    seen = {init: None}
    def solution(s):
        t = seen[s]
        if t is None: return [s]
        return solution(t) + [s]
    while Q:
        s = Q.popleft()
        for t in s.accessible():
            if t.success():
                seen[t] = s
                return solution(t)
            if t.safe() and t not in seen:
                Q.append(t)
                seen[t] = s

for s in solve():
    print(s)