# Eulerweg Eulerkreis

# Dieser Algorithmus liefert nicht nur die Entscheidung, ob ein ungerichteter
# zusammenhaengender Graph einen Eulerweg oder einen Eulerkreis besitzt,
# sondern gibt ggf. auch einen moeglichen Eulerweg oder Eulerkreis an.

# Voraussetzungen: 
# Die n Knoten des Graphen werden fortlaufend mit 0, 1, 2, . . . , n-1 bezeichnet.
# Die Kanten des Graphen sind ungerichtet, so dass
# die Adjazenzmatrix symmetrisch ist: a[i][j] = a[j][i],  0 <= i,j <= n-1
# Der Graph enthaelt keine Schlingen als Kanten,
# folglich besteht die Diagonale der Adjazenzmatrix aus lauter Nullen.
# Die Berechnung eines Eulerwegs setzt voraus, dass es keine parallele Kanten gibt,
# dass also je zwei Knoten durch höchstens 1 Kante verbunden sind.

# a = [[0] * m for i in range(n)]
# erzeugt eine zweidimensionale Liste mit n Komponenten, wobei jede dieser
# Komponenten ihrerseits eine Liste mit m Komponenten ist; jede Komponente
# a[i][j], 0 <= i <= n-1, 0 <= j <= m-1, erhaelt den Wert 0 zugewiesen.
# i = Zeilenindex, j = Spaltenindex


from collections import defaultdict

# This class represents an undirected graph using adjacency list representation
class Graph:

	def __init__(self,vertices):
		self.V= vertices #No. of vertices
		self.graph = defaultdict(list) # default dictionary to store graph
		self.Time = 0

	# function to add an edge to graph
	def addEdge(self,u,v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	# This function removes edge u-v from graph 
	def rmvEdge(self, u, v):
		for index, key in enumerate(self.graph[u]):
			if key == v:
				self.graph[u].pop(index)
		for index, key in enumerate(self.graph[v]):
			if key == u:
				self.graph[v].pop(index)

	# A DFS based function to count reachable vertices from v
	def DFSCount(self, v, visited):
		count = 1
		visited[v] = True
		for i in self.graph[v]:
			if visited[i] == False:
				count = count + self.DFSCount(i, visited)		 
		return count

	# The function to check if edge u-v can be considered as next edge in
	# Euler Tour
	def isValidNextEdge(self, u, v):
		# The edge u-v is valid in one of the following two cases:

		# 1) If v is the only adjacent vertex of u
		if len(self.graph[u]) == 1:
			return True
		else:
			'''
			2) If there are multiple adjacents, then u-v is not a bridge
				Do following steps to check if u-v is a bridge

			   2.a) count of vertices reachable from u'''
			visited =[False]*(self.V)
			count1 = self.DFSCount(u, visited)

			'''2.b) Remove edge (u, v) and after removing the edge, count
				vertices reachable from u'''
			self.rmvEdge(u, v)
			visited =[False]*(self.V)
			count2 = self.DFSCount(u, visited)

			#2.c) Add the edge back to the graph
			self.addEdge(u,v)

			# 2.d) If count1 is greater, then edge (u, v) is a bridge
			return False if count1 > count2 else True


	# Print Euler tour starting from vertex u
	def printEulerUtil(self, u):
		#Recur for all the vertices adjacent to this vertex
		for v in self.graph[u]:
			#If edge u-v is not removed and it's a a valid next edge
			if self.isValidNextEdge(u, v):
				print("%d -> %d" %(u,v)),
				self.rmvEdge(u, v)
				self.printEulerUtil(v)

	
	'''The main function that print Eulerian Trail. It first finds an odd
           degree vertex (if there is any) and then calls printEulerUtil()
           to print the path '''
	def printEulerTour(self):
		#Find a vertex with odd degree
		u = 0
		for i in range(self.V):
			if len(self.graph[i]) %2 != 0 :
				u = i
				break
		# Print tour starting from odd vertex
		print() # print ("\n")
		self.printEulerUtil(u)


ans = 'y'

while ans == 'y':

  n = int(input('Anzahl der Knoten: '))

# Erzeugen einer n x n - Matrix mit lauter Nullen
  a = [[0] * n for i in range(n)]

# Eingabe der Adjazenzmatrix
  for i in range(n):
     for j in range(i+1,n):
        print('a(',i,',',j,') = ', end = "")
        a[i][j] = int(input())
        a[j][i] = a[i][j]

# Ausgabe der Adjazenzmatrix
  print('Adjazenzmatrix:')
  print(a)
  for i in range(n): print(a[i])

# Berechnung des Grades von jedem der n Knoten
# Der Grad eines jeden der n Knoten wird in der
# aus n Komponenten bestehenden Liste g abgelegt.
  g = [0]*n   # Erzeugen der Liste g mit lauter Nullen
  for i in range(n):
     for j in range(n): g[i] = g[i] + a[i][j]

# Ausgabe des Grades eines jeden Knotens
  print('Knotengrade:')
  print(g)


# Decision according to Euler's Theorem
  anzahl = 0
  for i in range(n):
     if g[i] % 2 != 0: anzahl = anzahl + 1

  if anzahl == 0 or anzahl == 2:
     if anzahl == 0:
       print('Der Grad jedes Knotens ist geradzahlig,')
       print('folglich hat der Graph einen Eulerkreis.')
       print()
       print('Eulerkreis:')
     else:
       print('Der Grad von genau zwei Knoten ist ungerade,')
       print('folglich besitzt der Graph einen Eulerweg,');
       print('aber keinen Eulerkreis.')
       print()
       print('Eulerweg:')
  else:
     if anzahl == 1: print('Da ',anzahl,' Knoten einen ungeraden Grad hat,')
     else:           print('Da ',anzahl,' Knoten einen ungeraden Grad haben,')
     print('besitzt der Graph weder einen Eulerkreis noch einen Eulerweg.')



# Creating a graph according to the adjacency matrix
# and computing an Eulerian trail

  if anzahl == 0 or anzahl == 2:
      g = Graph(n)
      for i in range(n):
         for j in range(i+1,n):
            if a[i][j] == 1: g.addEdge(i,j)
      g.printEulerTour()

  print('\n')
  ans = input('Neuer Graph? <y> <n> ')
  print('\n')