from sage.all import *

fi = file('eul10c.g6', 'r')
lines = fi.readlines()
fi.close()

def is_eulerian(G, trail):
  edges = G.edges()
  if len(trail) is not len(edges):
    return False
  for e in trail:
    if e not in edges: return False
  return True

def trail(used):
  return map(lambda x: (min(x), max(x), None), used)

def algo(G, dfs):
  def score(v):
    return len(dfs) - dfs.index(v)

  v = dfs[0]
  used = []
  while True:
    found = False
    for z in sorted(G.neighbors(v), key=score):
      e = set([v, z])
      if e not in used:
        found = True
        v = z
        used += [e]
        break
    if not found:
      return used

for line in lines:
  G = Graph(line, sparse=True)
  dfs = list(G.depth_first_search(0))

  if not is_eulerian(G, trail(algo(G, dfs))):
    print map(lambda x: (x[0], x[1]), G.edges())
    print dfs
    print trail(algo(G, dfs))
    break