# Due to a bus breaking down, n people need to cross a bridge at
# night. They have one flashlight between them, which means that at
# most two people can cross the bridge at any given time. The people
# all take a different constant amount of time to cross, and when two
# people cross, they must travel at the slower of the two paces. Find
# the quickest crossing strategy as a function of the people's
# crossing speeds. (Strategy depends on speed, because optimal
# strategy is different for [1,2,5,10] than [1,4,5,10]. In fact, the strategy changes depending on what B-A is relative to D-C.


# Note to self: imagine Tufte-style whisker graphs for representing
# a state of the game. (One side of the river or the other.)

def append_maximal(coll, x, comp, append_ties = True) :
    """Given a list of maximal elements coll, return a new list of maximal
elements with x appended. The append_ties flag determines whether a
new element that ties with an old elment is allowed.

    """

    found_tie = False
    ret = []
    for y in coll :
        c = comp(x,y)
        if c == -1 : # x < y
            return coll
        elif c != 1 : # x equal or incomparable to y
            found_tie = found_tie or (c == 0)
            ret += [y]
    if append_ties or not found_tie :
        return ret + [x]
    else :
        return ret

def poly_increment(poly, index) :
    return [poly[i] + int(i == index) for i in range(len(poly))]

def poly_new(n) :
    return [0] * n


def poly_compare_faster(xs, ys) :
    # Same effect as poly_compare but optimized for speed rather than
    # readability.

    if xs == ys :
        return 0

    cumulative = 0
    sign = 0

    for (x,y) in reversed(zip(xs, ys)) :
        cumulative += y - x

        if cumulative != 0 :
            if (cumulative > 0) != (sign > 0) :
                return None
            sign = 1 if cumulative > 0 else -1
        #if cumulative * sign < 0 :
        #    return None
        #sign = sign or cumulative
        

        # if cumulative : 
        #    sign = 1 if cumulative > 0 else -1
        #    elif (cumulative > 0) != (sign > 0) :
        #        return None
    return sign
        #return 1 if sign > 0 else -1
        
    

def pretty_state(s) :
    return "".join([u'\u2E22' if x > 0 else u'\u2E24' for x in s])

def pretty_actions(actions) :
    ret = []
    n = max(map(max, actions))+1
    s = new_state(n)
    ret += [pretty_state(s)]
    for a in actions :
        s = apply_action(s, a)
        ret += [pretty_state(s)]
    return ret
    

def poly_compare(xs, ys) :
    # Ensure that the differences between these integer lists are
    # compatible with being properly-nested parentheses. Negatives
    # count one type of parens while positives count the other type.
    
    # NOTE: The above description is incorrect, but the algorithm is
    # correct and works as intended.

    cumulative = 0
    partial_sums = []

    for (x,y) in reversed(zip(xs,ys)) :
        cumulative += y-x
        partial_sums += [cumulative]

    if all([u == 0 for u in partial_sums]) :
        return 0
    elif all([u <= 0 for u in partial_sums])  :
        return -1
    elif all([u >= 0 for u in partial_sums]) :
        return 1
    else :
        return None
        
    
    
    # if xs != ys :
    #     if all([x >= y for (x,y) in zip(xs,ys)]) :
    #         return 1
    #     elif all([x <= y for (x,y) in zip(xs, ys)]) :
    #         return -1
    
    # cumulative = 0
    # sign = 0
    # for (x,y) in zip(xs, ys) :
    #     cumulative += y - x
    #     if cumulative != 0 :
    #         if sign != 0 and (cumulative > 0) != (sign > 0) :
    #             return None
    #         sign = 1 if cumulative > 0 else -1

    # if cumulative != 0 :
    #     return None
    # return sign


poly_compare = poly_compare_faster

def poly_compare_reverse(xs, ys) :
    r = poly_compare(xs, ys)
    return r if r is None else -r
    

def new_state(n) :
    return poly_new(n)

def is_goal_state(state) :
    return all(state)

def next_actions(state, flashlight_side=0) :
    ns = [i for i in range(len(state)) if state[i] == flashlight_side]
    A = [(x,) for x in ns]
    B = [(x,y) for x in ns for y in ns if x < y]

    return B + A if flashlight_side == 0 else A + B

def apply_action(state, action) :
    return [1-state[i] if i in action else state[i] for i in range(len(state))]

include_symmetry = True

def invert_node((state, flashlight)) :
    return (tuple(apply_action(state, range(len(state)))), (1+flashlight)%2)

def find_paths(n) :
    state = new_state(n)
    start_node = {"path" : [state], "actions" : [], "length" : poly_new(n)}

    seen = []
    extended = {}
    agenda = [start_node]

    while agenda :
        node = agenda.pop(0)

        # print node
        flashlight = (1+len(node["path"])) % 2
        state = node["path"][0]
        q = (tuple(state), flashlight)
        
        
        ext = append_maximal(extended.get(q, []), node, lambda a,b:poly_compare(a["length"],b["length"]), False)
 #       if include_symmetry  :
#            q_symmetric = invert_node(q)
            # ext = append_maximal(extended.get(q_symmetric, []), node, lambda a,b:poly_compare(a["length"],b["length"]), False)
        
        
        if ext != extended.get(q, []) :
            # found a shorter path than before
            extended[q] = ext


            if is_goal_state(state) :
                continue
            else :
                next_nodes = [{"path" : [t] + node["path"],
                               "actions" : node["actions"] + [a],
                               "length" : poly_increment(node["length"], a[-1])}
                              for a in next_actions(state, flashlight)
                              for t in [apply_action(state, a)]
                              if t not in node["path"]]
                agenda = next_nodes + agenda
    return extended.get((tuple([1]*n), 1))


# print pretty_state(new_state(8))

E = find_paths(4)

# print poly_compare([2,1,1,1],[2,3,1,1])
print 
for e in E :
    print e["actions"], e["length"]
    print "  ".join(pretty_actions(e["actions"]))
    print